java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.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/025-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:35:28,861 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:35:28,864 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:35:28,876 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:35:28,877 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:35:28,878 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:35:28,879 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:35:28,881 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:35:28,883 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:35:28,884 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:35:28,884 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:35:28,885 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:35:28,885 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:35:28,887 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:35:28,889 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:35:28,892 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:35:28,894 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:35:28,901 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:35:28,903 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:35:28,904 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:35:28,908 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:35:28,910 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:35:28,910 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:35:28,910 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:35:28,911 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:35:28,912 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:35:28,913 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:35:28,913 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:35:28,914 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:35:28,915 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:35:28,915 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:35:28,916 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:35:28,916 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:35:28,917 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:35:28,917 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:35:28,918 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:35:28,931 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:35:28,931 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:35:28,932 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:35:28,932 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:35:28,933 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:35:28,933 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:35:28,933 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:35:28,933 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:35:28,934 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:35:28,934 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:35:28,934 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:35:28,934 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:35:28,934 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:35:28,935 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:35:28,935 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:35:28,935 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:35:28,935 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:35:28,936 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:35:28,937 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:35:28,979 INFO ]: Repository-Root is: /tmp [2018-06-22 01:35:28,995 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:35:29,002 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:35:29,003 INFO ]: Initializing SmtParser... [2018-06-22 01:35:29,004 INFO ]: SmtParser initialized [2018-06-22 01:35:29,004 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/025-horn.smt2 [2018-06-22 01:35:29,006 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-22 01:35:29,100 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/025-horn.smt2 unknown [2018-06-22 01:35:29,364 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/025-horn.smt2 [2018-06-22 01:35:29,369 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:35:29,374 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:35:29,375 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:35:29,375 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:35:29,375 INFO ]: ChcToBoogie initialized [2018-06-22 01:35:29,378 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,459 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29 Unit [2018-06-22 01:35:29,459 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:35:29,460 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:35:29,460 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:35:29,460 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:35:29,484 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,484 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,491 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,491 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,497 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,503 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,505 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (1/1) ... [2018-06-22 01:35:29,507 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:35:29,508 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:35:29,508 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:35:29,508 INFO ]: RCFGBuilder initialized [2018-06-22 01:35:29,509 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (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-22 01:35:29,524 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:35:29,524 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:35:29,524 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:35:29,524 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:35:29,524 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:35:29,524 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-22 01:35:30,031 INFO ]: Using library mode [2018-06-22 01:35:30,031 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:35:30 BoogieIcfgContainer [2018-06-22 01:35:30,032 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:35:30,033 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:35:30,033 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:35:30,036 INFO ]: TraceAbstraction initialized [2018-06-22 01:35:30,036 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:35:29" (1/3) ... [2018-06-22 01:35:30,037 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@733bba6d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:35:30, skipping insertion in model container [2018-06-22 01:35:30,037 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:35:29" (2/3) ... [2018-06-22 01:35:30,038 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@733bba6d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:35:30, skipping insertion in model container [2018-06-22 01:35:30,038 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:35:30" (3/3) ... [2018-06-22 01:35:30,039 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:35:30,049 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:35:30,058 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:35:30,094 INFO ]: Using default assertion order modulation [2018-06-22 01:35:30,095 INFO ]: Interprodecural is true [2018-06-22 01:35:30,095 INFO ]: Hoare is false [2018-06-22 01:35:30,095 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:35:30,095 INFO ]: Backedges is TWOTRACK [2018-06-22 01:35:30,095 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:35:30,095 INFO ]: Difference is false [2018-06-22 01:35:30,095 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:35:30,095 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:35:30,111 INFO ]: Start isEmpty. Operand 12 states. [2018-06-22 01:35:30,123 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 01:35:30,123 INFO ]: Found error trace [2018-06-22 01:35:30,124 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:30,124 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:30,128 INFO ]: Analyzing trace with hash 1047244934, now seen corresponding path program 1 times [2018-06-22 01:35:30,129 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:30,129 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:30,166 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:30,166 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:30,166 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:30,213 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:30,485 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 19 [2018-06-22 01:35:30,488 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:30,489 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:35:30,489 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:35:30,491 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:35:30,502 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:35:30,502 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:35:30,504 INFO ]: Start difference. First operand 12 states. Second operand 3 states. [2018-06-22 01:35:30,737 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:30,737 INFO ]: Finished difference Result 15 states and 52 transitions. [2018-06-22 01:35:30,738 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:35:30,739 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 01:35:30,739 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:30,748 INFO ]: With dead ends: 15 [2018-06-22 01:35:30,748 INFO ]: Without dead ends: 15 [2018-06-22 01:35:30,750 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:35:30,767 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 01:35:30,785 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 11. [2018-06-22 01:35:30,786 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 01:35:30,787 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 42 transitions. [2018-06-22 01:35:30,788 INFO ]: Start accepts. Automaton has 11 states and 42 transitions. Word has length 7 [2018-06-22 01:35:30,789 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:30,789 INFO ]: Abstraction has 11 states and 42 transitions. [2018-06-22 01:35:30,789 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:35:30,789 INFO ]: Start isEmpty. Operand 11 states and 42 transitions. [2018-06-22 01:35:30,790 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:35:30,791 INFO ]: Found error trace [2018-06-22 01:35:30,791 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:30,791 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:30,791 INFO ]: Analyzing trace with hash -1911148730, now seen corresponding path program 1 times [2018-06-22 01:35:30,791 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:30,791 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:30,792 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:30,792 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:30,792 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:30,802 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:30,867 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:30,867 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:35:30,867 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:35:30,868 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:35:30,868 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:35:30,869 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:35:30,869 INFO ]: Start difference. First operand 11 states and 42 transitions. Second operand 3 states. [2018-06-22 01:35:31,040 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:31,040 INFO ]: Finished difference Result 15 states and 52 transitions. [2018-06-22 01:35:31,041 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:35:31,041 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:35:31,041 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:31,041 INFO ]: With dead ends: 15 [2018-06-22 01:35:31,041 INFO ]: Without dead ends: 15 [2018-06-22 01:35:31,042 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-22 01:35:31,042 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 01:35:31,044 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 12. [2018-06-22 01:35:31,045 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 01:35:31,045 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 46 transitions. [2018-06-22 01:35:31,045 INFO ]: Start accepts. Automaton has 12 states and 46 transitions. Word has length 8 [2018-06-22 01:35:31,045 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:31,045 INFO ]: Abstraction has 12 states and 46 transitions. [2018-06-22 01:35:31,045 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:35:31,046 INFO ]: Start isEmpty. Operand 12 states and 46 transitions. [2018-06-22 01:35:31,049 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:35:31,049 INFO ]: Found error trace [2018-06-22 01:35:31,049 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:31,049 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:31,049 INFO ]: Analyzing trace with hash -1892976220, now seen corresponding path program 1 times [2018-06-22 01:35:31,049 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:31,049 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:31,050 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,050 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:31,050 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,063 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:31,093 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:31,093 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:35:31,093 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:35:31,093 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:35:31,093 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:35:31,094 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:35:31,094 INFO ]: Start difference. First operand 12 states and 46 transitions. Second operand 3 states. [2018-06-22 01:35:31,266 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:31,266 INFO ]: Finished difference Result 10 states and 26 transitions. [2018-06-22 01:35:31,266 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:35:31,266 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:35:31,266 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:31,267 INFO ]: With dead ends: 10 [2018-06-22 01:35:31,267 INFO ]: Without dead ends: 9 [2018-06-22 01:35:31,267 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-22 01:35:31,267 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 01:35:31,268 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 01:35:31,268 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 01:35:31,268 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 17 transitions. [2018-06-22 01:35:31,268 INFO ]: Start accepts. Automaton has 9 states and 17 transitions. Word has length 8 [2018-06-22 01:35:31,268 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:31,269 INFO ]: Abstraction has 9 states and 17 transitions. [2018-06-22 01:35:31,269 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:35:31,269 INFO ]: Start isEmpty. Operand 9 states and 17 transitions. [2018-06-22 01:35:31,269 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:35:31,269 INFO ]: Found error trace [2018-06-22 01:35:31,269 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:31,269 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:31,269 INFO ]: Analyzing trace with hash -1937007318, now seen corresponding path program 1 times [2018-06-22 01:35:31,269 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:31,269 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:31,270 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,270 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:31,270 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,279 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:31,304 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:31,304 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:31,304 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-22 01:35:31,312 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:31,327 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:31,332 INFO ]: Computing forward predicates... [2018-06-22 01:35:31,350 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:31,382 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:31,382 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:35:31,382 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:35:31,382 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:35:31,382 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:35:31,383 INFO ]: Start difference. First operand 9 states and 17 transitions. Second operand 4 states. [2018-06-22 01:35:31,684 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:31,684 INFO ]: Finished difference Result 10 states and 23 transitions. [2018-06-22 01:35:31,685 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 01:35:31,685 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-22 01:35:31,685 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:31,685 INFO ]: With dead ends: 10 [2018-06-22 01:35:31,685 INFO ]: Without dead ends: 10 [2018-06-22 01:35:31,685 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:35:31,686 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 01:35:31,687 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 01:35:31,687 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 01:35:31,687 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 23 transitions. [2018-06-22 01:35:31,687 INFO ]: Start accepts. Automaton has 10 states and 23 transitions. Word has length 8 [2018-06-22 01:35:31,688 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:31,688 INFO ]: Abstraction has 10 states and 23 transitions. [2018-06-22 01:35:31,688 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:35:31,688 INFO ]: Start isEmpty. Operand 10 states and 23 transitions. [2018-06-22 01:35:31,688 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:35:31,688 INFO ]: Found error trace [2018-06-22 01:35:31,688 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:31,688 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:31,688 INFO ]: Analyzing trace with hash -1929619150, now seen corresponding path program 1 times [2018-06-22 01:35:31,688 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:31,688 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:31,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,689 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:31,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,696 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:31,721 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:31,721 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:35:31,721 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:35:31,721 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:35:31,721 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:35:31,721 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:35:31,721 INFO ]: Start difference. First operand 10 states and 23 transitions. Second operand 3 states. [2018-06-22 01:35:31,770 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:31,770 INFO ]: Finished difference Result 12 states and 35 transitions. [2018-06-22 01:35:31,770 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:35:31,771 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:35:31,771 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:31,771 INFO ]: With dead ends: 12 [2018-06-22 01:35:31,771 INFO ]: Without dead ends: 12 [2018-06-22 01:35:31,771 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-22 01:35:31,771 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 01:35:31,773 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 10. [2018-06-22 01:35:31,773 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 01:35:31,773 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 23 transitions. [2018-06-22 01:35:31,773 INFO ]: Start accepts. Automaton has 10 states and 23 transitions. Word has length 8 [2018-06-22 01:35:31,773 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:31,773 INFO ]: Abstraction has 10 states and 23 transitions. [2018-06-22 01:35:31,773 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:35:31,773 INFO ]: Start isEmpty. Operand 10 states and 23 transitions. [2018-06-22 01:35:31,774 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:35:31,774 INFO ]: Found error trace [2018-06-22 01:35:31,774 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:31,774 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:31,774 INFO ]: Analyzing trace with hash -1914842814, now seen corresponding path program 1 times [2018-06-22 01:35:31,774 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:31,774 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:31,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,775 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:31,775 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:31,785 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:31,865 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:31,865 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:31,865 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-22 01:35:31,871 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:31,886 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:31,888 INFO ]: Computing forward predicates... [2018-06-22 01:35:31,917 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:31,941 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:31,941 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 01:35:31,941 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:35:31,941 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:35:31,941 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:35:31,941 INFO ]: Start difference. First operand 10 states and 23 transitions. Second operand 5 states. [2018-06-22 01:35:32,213 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:32,213 INFO ]: Finished difference Result 13 states and 41 transitions. [2018-06-22 01:35:32,213 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:35:32,213 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 01:35:32,213 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:32,214 INFO ]: With dead ends: 13 [2018-06-22 01:35:32,214 INFO ]: Without dead ends: 13 [2018-06-22 01:35:32,214 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:35:32,214 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 01:35:32,215 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 10. [2018-06-22 01:35:32,215 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 01:35:32,216 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 23 transitions. [2018-06-22 01:35:32,216 INFO ]: Start accepts. Automaton has 10 states and 23 transitions. Word has length 8 [2018-06-22 01:35:32,216 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:32,216 INFO ]: Abstraction has 10 states and 23 transitions. [2018-06-22 01:35:32,216 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:35:32,216 INFO ]: Start isEmpty. Operand 10 states and 23 transitions. [2018-06-22 01:35:32,216 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:35:32,216 INFO ]: Found error trace [2018-06-22 01:35:32,216 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:32,216 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:32,216 INFO ]: Analyzing trace with hash 44147466, now seen corresponding path program 1 times [2018-06-22 01:35:32,216 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:32,216 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:32,219 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:32,219 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:32,219 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:32,238 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:32,320 INFO ]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:32,321 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:35:32,321 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:35:32,321 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:35:32,321 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:35:32,321 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:35:32,321 INFO ]: Start difference. First operand 10 states and 23 transitions. Second operand 3 states. [2018-06-22 01:35:32,380 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:32,380 INFO ]: Finished difference Result 10 states and 19 transitions. [2018-06-22 01:35:32,381 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:35:32,381 INFO ]: Start accepts. Automaton has 3 states. Word has length 9 [2018-06-22 01:35:32,381 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:32,381 INFO ]: With dead ends: 10 [2018-06-22 01:35:32,381 INFO ]: Without dead ends: 10 [2018-06-22 01:35:32,381 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-22 01:35:32,381 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 01:35:32,382 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 01:35:32,382 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 01:35:32,383 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 19 transitions. [2018-06-22 01:35:32,383 INFO ]: Start accepts. Automaton has 10 states and 19 transitions. Word has length 9 [2018-06-22 01:35:32,383 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:32,383 INFO ]: Abstraction has 10 states and 19 transitions. [2018-06-22 01:35:32,383 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:35:32,383 INFO ]: Start isEmpty. Operand 10 states and 19 transitions. [2018-06-22 01:35:32,384 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:35:32,384 INFO ]: Found error trace [2018-06-22 01:35:32,384 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:32,384 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:32,384 INFO ]: Analyzing trace with hash 73700138, now seen corresponding path program 1 times [2018-06-22 01:35:32,384 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:32,384 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:32,385 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:32,385 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:32,385 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:32,399 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:32,463 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:32,463 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:32,463 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:35:32,469 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:32,494 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:32,496 INFO ]: Computing forward predicates... [2018-06-22 01:35:32,763 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:32,796 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:32,796 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 7 [2018-06-22 01:35:32,796 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:35:32,797 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:35:32,797 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:32,797 INFO ]: Start difference. First operand 10 states and 19 transitions. Second operand 7 states. [2018-06-22 01:35:32,991 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:32,991 INFO ]: Finished difference Result 17 states and 47 transitions. [2018-06-22 01:35:32,992 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:35:32,992 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-22 01:35:32,992 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:32,992 INFO ]: With dead ends: 17 [2018-06-22 01:35:32,992 INFO ]: Without dead ends: 17 [2018-06-22 01:35:32,993 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:35:32,993 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 01:35:32,995 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 13. [2018-06-22 01:35:32,995 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 01:35:32,995 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 31 transitions. [2018-06-22 01:35:32,995 INFO ]: Start accepts. Automaton has 13 states and 31 transitions. Word has length 9 [2018-06-22 01:35:32,995 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:32,995 INFO ]: Abstraction has 13 states and 31 transitions. [2018-06-22 01:35:32,995 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:35:32,995 INFO ]: Start isEmpty. Operand 13 states and 31 transitions. [2018-06-22 01:35:32,996 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:35:32,996 INFO ]: Found error trace [2018-06-22 01:35:32,996 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:32,996 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:32,996 INFO ]: Analyzing trace with hash 302733346, now seen corresponding path program 1 times [2018-06-22 01:35:32,996 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:32,996 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:32,997 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:32,997 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:32,997 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:33,018 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:33,054 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:33,054 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:33,054 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-22 01:35:33,062 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:33,081 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:33,083 INFO ]: Computing forward predicates... [2018-06-22 01:35:33,193 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:33,215 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:33,215 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2018-06-22 01:35:33,216 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:35:33,216 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:35:33,216 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:35:33,216 INFO ]: Start difference. First operand 13 states and 31 transitions. Second operand 5 states. [2018-06-22 01:35:33,266 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:33,266 INFO ]: Finished difference Result 16 states and 43 transitions. [2018-06-22 01:35:33,267 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 01:35:33,267 INFO ]: Start accepts. Automaton has 5 states. Word has length 9 [2018-06-22 01:35:33,267 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:33,268 INFO ]: With dead ends: 16 [2018-06-22 01:35:33,268 INFO ]: Without dead ends: 16 [2018-06-22 01:35:33,268 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 9 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:35:33,268 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-22 01:35:33,269 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 14. [2018-06-22 01:35:33,269 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 01:35:33,270 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2018-06-22 01:35:33,270 INFO ]: Start accepts. Automaton has 14 states and 35 transitions. Word has length 9 [2018-06-22 01:35:33,270 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:33,270 INFO ]: Abstraction has 14 states and 35 transitions. [2018-06-22 01:35:33,270 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:35:33,270 INFO ]: Start isEmpty. Operand 14 states and 35 transitions. [2018-06-22 01:35:33,271 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:35:33,271 INFO ]: Found error trace [2018-06-22 01:35:33,271 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:33,271 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:33,271 INFO ]: Analyzing trace with hash 291651094, now seen corresponding path program 1 times [2018-06-22 01:35:33,271 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:33,271 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:33,272 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:33,272 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:33,272 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:33,281 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:33,310 INFO ]: Checked inductivity of 3 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:33,310 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:33,310 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-22 01:35:33,316 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:33,326 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:33,328 INFO ]: Computing forward predicates... [2018-06-22 01:35:33,427 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:33,447 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:33,447 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 7 [2018-06-22 01:35:33,447 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:35:33,448 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:35:33,448 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:33,448 INFO ]: Start difference. First operand 14 states and 35 transitions. Second operand 7 states. [2018-06-22 01:35:33,625 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:33,625 INFO ]: Finished difference Result 28 states and 86 transitions. [2018-06-22 01:35:33,626 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:35:33,626 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-22 01:35:33,626 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:33,627 INFO ]: With dead ends: 28 [2018-06-22 01:35:33,627 INFO ]: Without dead ends: 28 [2018-06-22 01:35:33,627 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:35:33,627 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-22 01:35:33,629 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 14. [2018-06-22 01:35:33,629 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 01:35:33,630 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2018-06-22 01:35:33,630 INFO ]: Start accepts. Automaton has 14 states and 35 transitions. Word has length 9 [2018-06-22 01:35:33,630 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:33,630 INFO ]: Abstraction has 14 states and 35 transitions. [2018-06-22 01:35:33,630 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:35:33,630 INFO ]: Start isEmpty. Operand 14 states and 35 transitions. [2018-06-22 01:35:33,630 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:35:33,630 INFO ]: Found error trace [2018-06-22 01:35:33,630 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:33,630 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:33,630 INFO ]: Analyzing trace with hash 749717510, now seen corresponding path program 2 times [2018-06-22 01:35:33,631 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:33,631 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:33,631 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:33,631 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:33,631 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:33,644 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:33,708 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:33,708 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:33,708 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-22 01:35:33,714 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:35:33,737 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:35:33,737 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:33,738 INFO ]: Computing forward predicates... [2018-06-22 01:35:33,767 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:33,788 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:33,788 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 7 [2018-06-22 01:35:33,789 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:35:33,789 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:35:33,789 INFO ]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:33,789 INFO ]: Start difference. First operand 14 states and 35 transitions. Second operand 7 states. [2018-06-22 01:35:35,932 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:35,932 INFO ]: Finished difference Result 21 states and 63 transitions. [2018-06-22 01:35:35,932 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:35:35,932 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-22 01:35:35,932 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:35,933 INFO ]: With dead ends: 21 [2018-06-22 01:35:35,933 INFO ]: Without dead ends: 21 [2018-06-22 01:35:35,933 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:35:35,933 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 01:35:35,935 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 15. [2018-06-22 01:35:35,935 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 01:35:35,935 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 39 transitions. [2018-06-22 01:35:35,935 INFO ]: Start accepts. Automaton has 15 states and 39 transitions. Word has length 9 [2018-06-22 01:35:35,935 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:35,935 INFO ]: Abstraction has 15 states and 39 transitions. [2018-06-22 01:35:35,935 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:35:35,935 INFO ]: Start isEmpty. Operand 15 states and 39 transitions. [2018-06-22 01:35:35,936 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:35:35,936 INFO ]: Found error trace [2018-06-22 01:35:35,936 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:35,936 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:35,936 INFO ]: Analyzing trace with hash 1932539318, now seen corresponding path program 1 times [2018-06-22 01:35:35,936 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:35,936 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:35,936 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:35,936 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:35,936 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:35,944 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:36,001 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:36,002 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:36,002 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-22 01:35:36,010 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:36,023 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:36,024 INFO ]: Computing forward predicates... [2018-06-22 01:35:36,078 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:36,100 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:36,100 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 01:35:36,100 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:35:36,100 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:35:36,100 INFO ]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:35:36,100 INFO ]: Start difference. First operand 15 states and 39 transitions. Second operand 8 states. [2018-06-22 01:35:36,190 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:36,190 INFO ]: Finished difference Result 23 states and 71 transitions. [2018-06-22 01:35:36,191 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 01:35:36,191 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 01:35:36,191 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:36,191 INFO ]: With dead ends: 23 [2018-06-22 01:35:36,191 INFO ]: Without dead ends: 23 [2018-06-22 01:35:36,192 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=73, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:35:36,192 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 01:35:36,194 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 16. [2018-06-22 01:35:36,194 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-22 01:35:36,194 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 43 transitions. [2018-06-22 01:35:36,194 INFO ]: Start accepts. Automaton has 16 states and 43 transitions. Word has length 10 [2018-06-22 01:35:36,194 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:36,194 INFO ]: Abstraction has 16 states and 43 transitions. [2018-06-22 01:35:36,194 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:35:36,194 INFO ]: Start isEmpty. Operand 16 states and 43 transitions. [2018-06-22 01:35:36,195 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:35:36,195 INFO ]: Found error trace [2018-06-22 01:35:36,195 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:36,195 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:36,195 INFO ]: Analyzing trace with hash 786183986, now seen corresponding path program 2 times [2018-06-22 01:35:36,195 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:36,195 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:36,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:36,196 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:36,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:36,204 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:36,312 INFO ]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:36,312 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:36,312 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-22 01:35:36,322 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:35:36,351 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:35:36,351 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:36,353 INFO ]: Computing forward predicates... [2018-06-22 01:35:36,450 INFO ]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:36,469 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:36,470 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-22 01:35:36,470 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:35:36,470 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:35:36,470 INFO ]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:35:36,470 INFO ]: Start difference. First operand 16 states and 43 transitions. Second operand 8 states. [2018-06-22 01:35:36,640 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:36,640 INFO ]: Finished difference Result 40 states and 120 transitions. [2018-06-22 01:35:36,641 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 01:35:36,641 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 01:35:36,641 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:36,641 INFO ]: With dead ends: 40 [2018-06-22 01:35:36,641 INFO ]: Without dead ends: 40 [2018-06-22 01:35:36,641 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:35:36,641 INFO ]: Start minimizeSevpa. Operand 40 states. [2018-06-22 01:35:36,645 INFO ]: Finished minimizeSevpa. Reduced states from 40 to 27. [2018-06-22 01:35:36,645 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 01:35:36,646 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 85 transitions. [2018-06-22 01:35:36,646 INFO ]: Start accepts. Automaton has 27 states and 85 transitions. Word has length 10 [2018-06-22 01:35:36,646 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:36,646 INFO ]: Abstraction has 27 states and 85 transitions. [2018-06-22 01:35:36,646 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:35:36,646 INFO ]: Start isEmpty. Operand 27 states and 85 transitions. [2018-06-22 01:35:36,647 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:35:36,647 INFO ]: Found error trace [2018-06-22 01:35:36,647 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:36,647 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:36,647 INFO ]: Analyzing trace with hash 775101734, now seen corresponding path program 1 times [2018-06-22 01:35:36,647 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:36,647 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:36,648 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:36,648 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:36,648 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:36,655 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:36,727 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:36,727 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:36,727 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-22 01:35:36,733 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:36,760 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:36,761 INFO ]: Computing forward predicates... [2018-06-22 01:35:36,800 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:36,819 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:36,820 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 01:35:36,820 INFO ]: Interpolant automaton has 6 states [2018-06-22 01:35:36,820 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 01:35:36,820 INFO ]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:35:36,820 INFO ]: Start difference. First operand 27 states and 85 transitions. Second operand 6 states. [2018-06-22 01:35:36,943 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:36,943 INFO ]: Finished difference Result 35 states and 113 transitions. [2018-06-22 01:35:36,943 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:35:36,943 INFO ]: Start accepts. Automaton has 6 states. Word has length 10 [2018-06-22 01:35:36,943 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:36,944 INFO ]: With dead ends: 35 [2018-06-22 01:35:36,944 INFO ]: Without dead ends: 35 [2018-06-22 01:35:36,944 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 10 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:36,944 INFO ]: Start minimizeSevpa. Operand 35 states. [2018-06-22 01:35:36,948 INFO ]: Finished minimizeSevpa. Reduced states from 35 to 28. [2018-06-22 01:35:36,948 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:35:36,949 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 89 transitions. [2018-06-22 01:35:36,949 INFO ]: Start accepts. Automaton has 28 states and 89 transitions. Word has length 10 [2018-06-22 01:35:36,949 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:36,949 INFO ]: Abstraction has 28 states and 89 transitions. [2018-06-22 01:35:36,949 INFO ]: Interpolant automaton has 6 states. [2018-06-22 01:35:36,949 INFO ]: Start isEmpty. Operand 28 states and 89 transitions. [2018-06-22 01:35:36,950 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:35:36,950 INFO ]: Found error trace [2018-06-22 01:35:36,950 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:36,950 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:36,950 INFO ]: Analyzing trace with hash 442634174, now seen corresponding path program 2 times [2018-06-22 01:35:36,950 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:36,950 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:36,951 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:36,951 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:35:36,951 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:36,958 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:37,154 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:37,154 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:37,154 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-22 01:35:37,160 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:35:37,172 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:35:37,172 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:37,173 INFO ]: Computing forward predicates... [2018-06-22 01:35:37,192 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:37,211 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:37,211 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 01:35:37,211 INFO ]: Interpolant automaton has 6 states [2018-06-22 01:35:37,211 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 01:35:37,211 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:35:37,212 INFO ]: Start difference. First operand 28 states and 89 transitions. Second operand 6 states. [2018-06-22 01:35:37,288 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:37,288 INFO ]: Finished difference Result 35 states and 109 transitions. [2018-06-22 01:35:37,288 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 01:35:37,288 INFO ]: Start accepts. Automaton has 6 states. Word has length 10 [2018-06-22 01:35:37,288 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:37,289 INFO ]: With dead ends: 35 [2018-06-22 01:35:37,289 INFO ]: Without dead ends: 35 [2018-06-22 01:35:37,289 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 9 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:35:37,289 INFO ]: Start minimizeSevpa. Operand 35 states. [2018-06-22 01:35:37,292 INFO ]: Finished minimizeSevpa. Reduced states from 35 to 28. [2018-06-22 01:35:37,292 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:35:37,297 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 89 transitions. [2018-06-22 01:35:37,297 INFO ]: Start accepts. Automaton has 28 states and 89 transitions. Word has length 10 [2018-06-22 01:35:37,298 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:37,298 INFO ]: Abstraction has 28 states and 89 transitions. [2018-06-22 01:35:37,298 INFO ]: Interpolant automaton has 6 states. [2018-06-22 01:35:37,298 INFO ]: Start isEmpty. Operand 28 states and 89 transitions. [2018-06-22 01:35:37,298 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:35:37,298 INFO ]: Found error trace [2018-06-22 01:35:37,298 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:37,298 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:37,298 INFO ]: Analyzing trace with hash 431551922, now seen corresponding path program 2 times [2018-06-22 01:35:37,298 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:37,298 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:37,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:37,299 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:37,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:37,305 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:37,421 INFO ]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:37,422 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:37,422 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-22 01:35:37,428 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:35:37,440 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:35:37,440 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:37,442 INFO ]: Computing forward predicates... [2018-06-22 01:35:39,065 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:39,093 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:39,093 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2018-06-22 01:35:39,093 INFO ]: Interpolant automaton has 9 states [2018-06-22 01:35:39,093 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 01:35:39,093 INFO ]: CoverageRelationStatistics Valid=15, Invalid=55, Unknown=2, NotChecked=0, Total=72 [2018-06-22 01:35:39,093 INFO ]: Start difference. First operand 28 states and 89 transitions. Second operand 9 states. [2018-06-22 01:35:44,540 WARN ]: Spent 645.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 76 [2018-06-22 01:35:48,740 WARN ]: Spent 1.60 s on a formula simplification. DAG size of input: 80 DAG size of output: 77 [2018-06-22 01:35:49,954 WARN ]: Spent 568.00 ms on a formula simplification that was a NOOP. DAG size: 58 [2018-06-22 01:35:51,882 WARN ]: Spent 1.32 s on a formula simplification. DAG size of input: 70 DAG size of output: 63 [2018-06-22 01:35:54,412 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:54,412 INFO ]: Finished difference Result 67 states and 230 transitions. [2018-06-22 01:35:54,413 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 01:35:54,413 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-22 01:35:54,413 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:54,414 INFO ]: With dead ends: 67 [2018-06-22 01:35:54,414 INFO ]: Without dead ends: 67 [2018-06-22 01:35:54,414 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=84, Invalid=182, Unknown=6, NotChecked=0, Total=272 [2018-06-22 01:35:54,414 INFO ]: Start minimizeSevpa. Operand 67 states. [2018-06-22 01:35:54,424 INFO ]: Finished minimizeSevpa. Reduced states from 67 to 27. [2018-06-22 01:35:54,424 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 01:35:54,425 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 83 transitions. [2018-06-22 01:35:54,425 INFO ]: Start accepts. Automaton has 27 states and 83 transitions. Word has length 10 [2018-06-22 01:35:54,425 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:54,425 INFO ]: Abstraction has 27 states and 83 transitions. [2018-06-22 01:35:54,425 INFO ]: Interpolant automaton has 9 states. [2018-06-22 01:35:54,425 INFO ]: Start isEmpty. Operand 27 states and 83 transitions. [2018-06-22 01:35:54,426 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:35:54,426 INFO ]: Found error trace [2018-06-22 01:35:54,426 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:54,426 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:54,426 INFO ]: Analyzing trace with hash -572988246, now seen corresponding path program 2 times [2018-06-22 01:35:54,426 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:54,426 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:54,426 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:54,427 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:54,427 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:54,439 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:54,501 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:54,501 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:54,501 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-22 01:35:54,509 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:35:54,532 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:35:54,532 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:54,534 INFO ]: Computing forward predicates... [2018-06-22 01:35:54,539 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:54,572 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:54,572 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-22 01:35:54,572 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:35:54,572 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:35:54,572 INFO ]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:54,572 INFO ]: Start difference. First operand 27 states and 83 transitions. Second operand 7 states. [2018-06-22 01:35:54,687 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:54,687 INFO ]: Finished difference Result 40 states and 135 transitions. [2018-06-22 01:35:54,687 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:35:54,687 INFO ]: Start accepts. Automaton has 7 states. Word has length 11 [2018-06-22 01:35:54,687 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:54,688 INFO ]: With dead ends: 40 [2018-06-22 01:35:54,688 INFO ]: Without dead ends: 40 [2018-06-22 01:35:54,688 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:54,688 INFO ]: Start minimizeSevpa. Operand 40 states. [2018-06-22 01:35:54,691 INFO ]: Finished minimizeSevpa. Reduced states from 40 to 26. [2018-06-22 01:35:54,691 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-22 01:35:54,692 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 79 transitions. [2018-06-22 01:35:54,692 INFO ]: Start accepts. Automaton has 26 states and 79 transitions. Word has length 11 [2018-06-22 01:35:54,692 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:54,692 INFO ]: Abstraction has 26 states and 79 transitions. [2018-06-22 01:35:54,692 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:35:54,692 INFO ]: Start isEmpty. Operand 26 states and 79 transitions. [2018-06-22 01:35:54,692 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:35:54,692 INFO ]: Found error trace [2018-06-22 01:35:54,692 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:54,692 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:54,692 INFO ]: Analyzing trace with hash -1750265170, now seen corresponding path program 3 times [2018-06-22 01:35:54,692 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:54,692 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:54,693 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:54,693 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:54,693 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:54,701 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:54,798 INFO ]: Checked inductivity of 10 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:54,798 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:54,798 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-22 01:35:54,804 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:35:54,820 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 01:35:54,820 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:54,821 INFO ]: Computing forward predicates... [2018-06-22 01:35:55,105 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:55,138 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:55,138 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 11 [2018-06-22 01:35:55,138 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:35:55,139 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:35:55,139 INFO ]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:35:55,139 INFO ]: Start difference. First operand 26 states and 79 transitions. Second operand 11 states. [2018-06-22 01:35:55,710 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:55,710 INFO ]: Finished difference Result 120 states and 419 transitions. [2018-06-22 01:35:55,710 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-22 01:35:55,710 INFO ]: Start accepts. Automaton has 11 states. Word has length 11 [2018-06-22 01:35:55,710 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:55,712 INFO ]: With dead ends: 120 [2018-06-22 01:35:55,712 INFO ]: Without dead ends: 120 [2018-06-22 01:35:55,712 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=163, Invalid=539, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:35:55,712 INFO ]: Start minimizeSevpa. Operand 120 states. [2018-06-22 01:35:55,718 INFO ]: Finished minimizeSevpa. Reduced states from 120 to 41. [2018-06-22 01:35:55,718 INFO ]: Start removeUnreachable. Operand 41 states. [2018-06-22 01:35:55,719 INFO ]: Finished removeUnreachable. Reduced from 41 states to 41 states and 139 transitions. [2018-06-22 01:35:55,719 INFO ]: Start accepts. Automaton has 41 states and 139 transitions. Word has length 11 [2018-06-22 01:35:55,719 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:55,719 INFO ]: Abstraction has 41 states and 139 transitions. [2018-06-22 01:35:55,719 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:35:55,719 INFO ]: Start isEmpty. Operand 41 states and 139 transitions. [2018-06-22 01:35:55,720 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:35:55,720 INFO ]: Found error trace [2018-06-22 01:35:55,720 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:55,720 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:55,720 INFO ]: Analyzing trace with hash 817060106, now seen corresponding path program 4 times [2018-06-22 01:35:55,720 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:55,720 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:55,720 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:55,720 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:55,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:55,729 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:55,841 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:55,841 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:55,841 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:35:55,849 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:35:55,864 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:35:55,864 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:55,865 INFO ]: Computing forward predicates... [2018-06-22 01:35:55,883 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:55,906 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:55,906 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-22 01:35:55,906 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:35:55,906 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:35:55,906 INFO ]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:35:55,906 INFO ]: Start difference. First operand 41 states and 139 transitions. Second operand 7 states. [2018-06-22 01:35:56,012 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:56,012 INFO ]: Finished difference Result 60 states and 207 transitions. [2018-06-22 01:35:56,013 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 01:35:56,013 INFO ]: Start accepts. Automaton has 7 states. Word has length 11 [2018-06-22 01:35:56,013 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:56,013 INFO ]: With dead ends: 60 [2018-06-22 01:35:56,013 INFO ]: Without dead ends: 60 [2018-06-22 01:35:56,013 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 10 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:35:56,013 INFO ]: Start minimizeSevpa. Operand 60 states. [2018-06-22 01:35:56,017 INFO ]: Finished minimizeSevpa. Reduced states from 60 to 42. [2018-06-22 01:35:56,017 INFO ]: Start removeUnreachable. Operand 42 states. [2018-06-22 01:35:56,018 INFO ]: Finished removeUnreachable. Reduced from 42 states to 42 states and 143 transitions. [2018-06-22 01:35:56,018 INFO ]: Start accepts. Automaton has 42 states and 143 transitions. Word has length 11 [2018-06-22 01:35:56,018 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:56,018 INFO ]: Abstraction has 42 states and 143 transitions. [2018-06-22 01:35:56,018 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:35:56,019 INFO ]: Start isEmpty. Operand 42 states and 143 transitions. [2018-06-22 01:35:56,019 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:35:56,019 INFO ]: Found error trace [2018-06-22 01:35:56,019 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:56,019 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:56,019 INFO ]: Analyzing trace with hash 484592546, now seen corresponding path program 5 times [2018-06-22 01:35:56,019 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:56,019 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:56,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:56,020 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:56,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:56,030 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:56,075 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:56,075 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:56,075 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:35:56,081 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:35:56,124 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2018-06-22 01:35:56,124 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:56,126 INFO ]: Computing forward predicates... [2018-06-22 01:35:56,243 INFO ]: Checked inductivity of 10 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:56,263 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:56,263 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 11 [2018-06-22 01:35:56,264 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:35:56,264 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:35:56,264 INFO ]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:35:56,264 INFO ]: Start difference. First operand 42 states and 143 transitions. Second operand 11 states. [2018-06-22 01:35:57,160 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:35:57,160 INFO ]: Finished difference Result 176 states and 631 transitions. [2018-06-22 01:35:57,161 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-22 01:35:57,161 INFO ]: Start accepts. Automaton has 11 states. Word has length 11 [2018-06-22 01:35:57,161 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:35:57,162 INFO ]: With dead ends: 176 [2018-06-22 01:35:57,162 INFO ]: Without dead ends: 176 [2018-06-22 01:35:57,163 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 276 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=306, Invalid=884, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:35:57,163 INFO ]: Start minimizeSevpa. Operand 176 states. [2018-06-22 01:35:57,167 INFO ]: Finished minimizeSevpa. Reduced states from 176 to 47. [2018-06-22 01:35:57,167 INFO ]: Start removeUnreachable. Operand 47 states. [2018-06-22 01:35:57,168 INFO ]: Finished removeUnreachable. Reduced from 47 states to 47 states and 163 transitions. [2018-06-22 01:35:57,168 INFO ]: Start accepts. Automaton has 47 states and 163 transitions. Word has length 11 [2018-06-22 01:35:57,168 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:35:57,168 INFO ]: Abstraction has 47 states and 163 transitions. [2018-06-22 01:35:57,168 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:35:57,168 INFO ]: Start isEmpty. Operand 47 states and 163 transitions. [2018-06-22 01:35:57,169 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:35:57,169 INFO ]: Found error trace [2018-06-22 01:35:57,169 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:35:57,169 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:35:57,169 INFO ]: Analyzing trace with hash -1706295418, now seen corresponding path program 3 times [2018-06-22 01:35:57,169 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:35:57,169 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:35:57,170 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:57,170 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:35:57,170 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:35:57,178 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:57,342 WARN ]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 01:35:57,824 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:57,824 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:35:57,824 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 01:35:57,838 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:35:57,897 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 01:35:57,897 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:35:57,899 INFO ]: Computing forward predicates... [2018-06-22 01:35:58,178 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:35:58,199 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:35:58,199 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2018-06-22 01:35:58,199 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:35:58,200 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:35:58,200 INFO ]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:35:58,200 INFO ]: Start difference. First operand 47 states and 163 transitions. Second operand 11 states. [2018-06-22 01:36:01,407 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:01,407 INFO ]: Finished difference Result 76 states and 271 transitions. [2018-06-22 01:36:01,408 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 01:36:01,408 INFO ]: Start accepts. Automaton has 11 states. Word has length 11 [2018-06-22 01:36:01,408 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:01,409 INFO ]: With dead ends: 76 [2018-06-22 01:36:01,409 INFO ]: Without dead ends: 76 [2018-06-22 01:36:01,409 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=110, Invalid=232, Unknown=0, NotChecked=0, Total=342 [2018-06-22 01:36:01,409 INFO ]: Start minimizeSevpa. Operand 76 states. [2018-06-22 01:36:01,417 INFO ]: Finished minimizeSevpa. Reduced states from 76 to 49. [2018-06-22 01:36:01,417 INFO ]: Start removeUnreachable. Operand 49 states. [2018-06-22 01:36:01,417 INFO ]: Finished removeUnreachable. Reduced from 49 states to 49 states and 171 transitions. [2018-06-22 01:36:01,417 INFO ]: Start accepts. Automaton has 49 states and 171 transitions. Word has length 11 [2018-06-22 01:36:01,418 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:01,418 INFO ]: Abstraction has 49 states and 171 transitions. [2018-06-22 01:36:01,418 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:36:01,418 INFO ]: Start isEmpty. Operand 49 states and 171 transitions. [2018-06-22 01:36:01,418 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:36:01,418 INFO ]: Found error trace [2018-06-22 01:36:01,418 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:01,418 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:01,418 INFO ]: Analyzing trace with hash -602463842, now seen corresponding path program 3 times [2018-06-22 01:36:01,418 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:01,418 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:01,419 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:01,419 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:01,419 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:01,426 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:01,766 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:01,766 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:01,766 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:01,774 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:36:01,792 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 01:36:01,792 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:01,793 INFO ]: Computing forward predicates... [2018-06-22 01:36:01,862 INFO ]: Checked inductivity of 15 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:01,889 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:01,890 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 01:36:01,890 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:01,890 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:01,890 INFO ]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:36:01,890 INFO ]: Start difference. First operand 49 states and 171 transitions. Second operand 14 states. [2018-06-22 01:36:02,658 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:02,658 INFO ]: Finished difference Result 117 states and 375 transitions. [2018-06-22 01:36:02,660 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 01:36:02,660 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-22 01:36:02,660 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:02,661 INFO ]: With dead ends: 117 [2018-06-22 01:36:02,661 INFO ]: Without dead ends: 100 [2018-06-22 01:36:02,661 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=102, Invalid=360, Unknown=0, NotChecked=0, Total=462 [2018-06-22 01:36:02,662 INFO ]: Start minimizeSevpa. Operand 100 states. [2018-06-22 01:36:02,672 INFO ]: Finished minimizeSevpa. Reduced states from 100 to 58. [2018-06-22 01:36:02,672 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-22 01:36:02,673 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 201 transitions. [2018-06-22 01:36:02,673 INFO ]: Start accepts. Automaton has 58 states and 201 transitions. Word has length 12 [2018-06-22 01:36:02,674 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:02,674 INFO ]: Abstraction has 58 states and 201 transitions. [2018-06-22 01:36:02,674 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:02,674 INFO ]: Start isEmpty. Operand 58 states and 201 transitions. [2018-06-22 01:36:02,674 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:36:02,674 INFO ]: Found error trace [2018-06-22 01:36:02,674 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:02,674 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:02,675 INFO ]: Analyzing trace with hash 1224189618, now seen corresponding path program 6 times [2018-06-22 01:36:02,675 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:02,675 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:02,675 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:02,675 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:02,675 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:02,686 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:02,743 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:02,762 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:02,762 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:02,782 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:36:02,799 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 01:36:02,799 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:02,800 INFO ]: Computing forward predicates... [2018-06-22 01:36:02,925 INFO ]: Checked inductivity of 15 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:02,944 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:02,944 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 01:36:02,944 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:02,944 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:02,944 INFO ]: CoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:36:02,944 INFO ]: Start difference. First operand 58 states and 201 transitions. Second operand 14 states. [2018-06-22 01:36:03,456 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:03,456 INFO ]: Finished difference Result 127 states and 443 transitions. [2018-06-22 01:36:03,456 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 01:36:03,456 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-22 01:36:03,456 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:03,457 INFO ]: With dead ends: 127 [2018-06-22 01:36:03,457 INFO ]: Without dead ends: 127 [2018-06-22 01:36:03,457 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=109, Invalid=397, Unknown=0, NotChecked=0, Total=506 [2018-06-22 01:36:03,457 INFO ]: Start minimizeSevpa. Operand 127 states. [2018-06-22 01:36:03,462 INFO ]: Finished minimizeSevpa. Reduced states from 127 to 61. [2018-06-22 01:36:03,462 INFO ]: Start removeUnreachable. Operand 61 states. [2018-06-22 01:36:03,463 INFO ]: Finished removeUnreachable. Reduced from 61 states to 61 states and 211 transitions. [2018-06-22 01:36:03,463 INFO ]: Start accepts. Automaton has 61 states and 211 transitions. Word has length 12 [2018-06-22 01:36:03,463 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:03,463 INFO ]: Abstraction has 61 states and 211 transitions. [2018-06-22 01:36:03,463 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:03,463 INFO ]: Start isEmpty. Operand 61 states and 211 transitions. [2018-06-22 01:36:03,464 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:36:03,464 INFO ]: Found error trace [2018-06-22 01:36:03,464 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:03,464 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:03,464 INFO ]: Analyzing trace with hash -460637890, now seen corresponding path program 7 times [2018-06-22 01:36:03,464 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:03,464 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:03,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:03,465 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:03,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:03,472 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:03,847 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:03,847 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:03,847 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:03,853 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:03,873 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:03,875 INFO ]: Computing forward predicates... [2018-06-22 01:36:04,093 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:04,112 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:04,112 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 01:36:04,112 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:04,112 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:04,112 INFO ]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:36:04,112 INFO ]: Start difference. First operand 61 states and 211 transitions. Second operand 14 states. [2018-06-22 01:36:04,827 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:04,827 INFO ]: Finished difference Result 190 states and 683 transitions. [2018-06-22 01:36:04,828 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-22 01:36:04,828 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-22 01:36:04,828 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:04,828 INFO ]: With dead ends: 190 [2018-06-22 01:36:04,828 INFO ]: Without dead ends: 190 [2018-06-22 01:36:04,829 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=219, Invalid=711, Unknown=0, NotChecked=0, Total=930 [2018-06-22 01:36:04,829 INFO ]: Start minimizeSevpa. Operand 190 states. [2018-06-22 01:36:04,833 INFO ]: Finished minimizeSevpa. Reduced states from 190 to 73. [2018-06-22 01:36:04,833 INFO ]: Start removeUnreachable. Operand 73 states. [2018-06-22 01:36:04,834 INFO ]: Finished removeUnreachable. Reduced from 73 states to 73 states and 255 transitions. [2018-06-22 01:36:04,834 INFO ]: Start accepts. Automaton has 73 states and 255 transitions. Word has length 12 [2018-06-22 01:36:04,834 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:04,834 INFO ]: Abstraction has 73 states and 255 transitions. [2018-06-22 01:36:04,834 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:04,834 INFO ]: Start isEmpty. Operand 73 states and 255 transitions. [2018-06-22 01:36:04,835 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:36:04,835 INFO ]: Found error trace [2018-06-22 01:36:04,835 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:04,835 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:04,835 INFO ]: Analyzing trace with hash 2117769638, now seen corresponding path program 8 times [2018-06-22 01:36:04,835 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:04,835 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:04,836 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:04,836 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:04,836 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:04,842 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:04,899 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:04,899 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:04,899 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:04,905 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:36:04,924 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:36:04,924 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:04,925 INFO ]: Computing forward predicates... [2018-06-22 01:36:04,950 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:04,969 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:04,969 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 01:36:04,969 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:36:04,969 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:36:04,969 INFO ]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:36:04,969 INFO ]: Start difference. First operand 73 states and 255 transitions. Second operand 8 states. [2018-06-22 01:36:05,090 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:05,090 INFO ]: Finished difference Result 130 states and 459 transitions. [2018-06-22 01:36:05,090 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 01:36:05,090 INFO ]: Start accepts. Automaton has 8 states. Word has length 12 [2018-06-22 01:36:05,091 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:05,091 INFO ]: With dead ends: 130 [2018-06-22 01:36:05,091 INFO ]: Without dead ends: 130 [2018-06-22 01:36:05,092 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 10 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=146, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:36:05,092 INFO ]: Start minimizeSevpa. Operand 130 states. [2018-06-22 01:36:05,094 INFO ]: Finished minimizeSevpa. Reduced states from 130 to 75. [2018-06-22 01:36:05,094 INFO ]: Start removeUnreachable. Operand 75 states. [2018-06-22 01:36:05,095 INFO ]: Finished removeUnreachable. Reduced from 75 states to 75 states and 263 transitions. [2018-06-22 01:36:05,095 INFO ]: Start accepts. Automaton has 75 states and 263 transitions. Word has length 12 [2018-06-22 01:36:05,095 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:05,095 INFO ]: Abstraction has 75 states and 263 transitions. [2018-06-22 01:36:05,095 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:36:05,095 INFO ]: Start isEmpty. Operand 75 states and 263 transitions. [2018-06-22 01:36:05,096 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:36:05,096 INFO ]: Found error trace [2018-06-22 01:36:05,096 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:05,096 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:05,096 INFO ]: Analyzing trace with hash 1785302078, now seen corresponding path program 9 times [2018-06-22 01:36:05,096 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:05,096 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:05,096 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:05,096 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:05,096 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:05,103 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:05,162 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:05,162 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:05,162 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:05,168 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:36:05,213 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 01:36:05,213 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:05,215 INFO ]: Computing forward predicates... [2018-06-22 01:36:05,331 INFO ]: Checked inductivity of 15 backedges. 2 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:05,350 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:05,350 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 01:36:05,350 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:05,350 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:05,350 INFO ]: CoverageRelationStatistics Valid=27, Invalid=155, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:36:05,350 INFO ]: Start difference. First operand 75 states and 263 transitions. Second operand 14 states. [2018-06-22 01:36:07,931 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:07,931 INFO ]: Finished difference Result 246 states and 871 transitions. [2018-06-22 01:36:07,972 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-06-22 01:36:07,972 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-22 01:36:07,972 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:07,974 INFO ]: With dead ends: 246 [2018-06-22 01:36:07,974 INFO ]: Without dead ends: 246 [2018-06-22 01:36:07,975 INFO ]: 0 DeclaredPredicates, 61 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 866 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=790, Invalid=2290, Unknown=0, NotChecked=0, Total=3080 [2018-06-22 01:36:07,975 INFO ]: Start minimizeSevpa. Operand 246 states. [2018-06-22 01:36:07,984 INFO ]: Finished minimizeSevpa. Reduced states from 246 to 73. [2018-06-22 01:36:07,984 INFO ]: Start removeUnreachable. Operand 73 states. [2018-06-22 01:36:08,007 INFO ]: Finished removeUnreachable. Reduced from 73 states to 73 states and 255 transitions. [2018-06-22 01:36:08,007 INFO ]: Start accepts. Automaton has 73 states and 255 transitions. Word has length 12 [2018-06-22 01:36:08,007 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:08,007 INFO ]: Abstraction has 73 states and 255 transitions. [2018-06-22 01:36:08,007 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:08,007 INFO ]: Start isEmpty. Operand 73 states and 255 transitions. [2018-06-22 01:36:08,008 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 01:36:08,008 INFO ]: Found error trace [2018-06-22 01:36:08,008 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:08,008 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:08,008 INFO ]: Analyzing trace with hash 1206651938, now seen corresponding path program 10 times [2018-06-22 01:36:08,008 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:08,008 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:08,009 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:08,009 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:08,009 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:08,023 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:08,208 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 01:36:09,050 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:09,050 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:09,050 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:09,063 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:36:09,110 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:36:09,110 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:09,113 INFO ]: Computing forward predicates... [2018-06-22 01:36:09,945 WARN ]: Spent 241.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2018-06-22 01:36:09,950 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:09,969 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:09,969 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2018-06-22 01:36:09,969 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:36:09,969 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:36:09,969 INFO ]: CoverageRelationStatistics Valid=31, Invalid=179, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:36:09,969 INFO ]: Start difference. First operand 73 states and 255 transitions. Second operand 15 states. [2018-06-22 01:36:17,642 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:17,642 INFO ]: Finished difference Result 95 states and 327 transitions. [2018-06-22 01:36:17,642 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-22 01:36:17,642 INFO ]: Start accepts. Automaton has 15 states. Word has length 13 [2018-06-22 01:36:17,642 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:17,643 INFO ]: With dead ends: 95 [2018-06-22 01:36:17,643 INFO ]: Without dead ends: 95 [2018-06-22 01:36:17,643 INFO ]: 0 DeclaredPredicates, 30 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=78, Invalid=474, Unknown=0, NotChecked=0, Total=552 [2018-06-22 01:36:17,643 INFO ]: Start minimizeSevpa. Operand 95 states. [2018-06-22 01:36:17,646 INFO ]: Finished minimizeSevpa. Reduced states from 95 to 77. [2018-06-22 01:36:17,646 INFO ]: Start removeUnreachable. Operand 77 states. [2018-06-22 01:36:17,647 INFO ]: Finished removeUnreachable. Reduced from 77 states to 77 states and 267 transitions. [2018-06-22 01:36:17,647 INFO ]: Start accepts. Automaton has 77 states and 267 transitions. Word has length 13 [2018-06-22 01:36:17,647 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:17,647 INFO ]: Abstraction has 77 states and 267 transitions. [2018-06-22 01:36:17,647 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:36:17,647 INFO ]: Start isEmpty. Operand 77 states and 267 transitions. [2018-06-22 01:36:17,648 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 01:36:17,648 INFO ]: Found error trace [2018-06-22 01:36:17,648 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:17,648 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:17,648 INFO ]: Analyzing trace with hash -509907830, now seen corresponding path program 11 times [2018-06-22 01:36:17,648 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:17,648 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:17,648 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:17,648 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:17,648 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:17,658 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:18,032 INFO ]: Checked inductivity of 21 backedges. 7 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:18,032 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:18,032 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:18,038 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:36:18,060 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 01:36:18,060 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:18,061 INFO ]: Computing forward predicates... [2018-06-22 01:36:18,091 INFO ]: Checked inductivity of 21 backedges. 7 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:18,109 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:18,109 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 01:36:18,109 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:36:18,110 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:36:18,110 INFO ]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:36:18,110 INFO ]: Start difference. First operand 77 states and 267 transitions. Second operand 8 states. [2018-06-22 01:36:18,221 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:18,221 INFO ]: Finished difference Result 94 states and 291 transitions. [2018-06-22 01:36:18,222 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 01:36:18,222 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 01:36:18,222 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:18,223 INFO ]: With dead ends: 94 [2018-06-22 01:36:18,223 INFO ]: Without dead ends: 78 [2018-06-22 01:36:18,223 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 11 SyntacticMatches, 3 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=54, Invalid=102, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:36:18,223 INFO ]: Start minimizeSevpa. Operand 78 states. [2018-06-22 01:36:18,226 INFO ]: Finished minimizeSevpa. Reduced states from 78 to 78. [2018-06-22 01:36:18,226 INFO ]: Start removeUnreachable. Operand 78 states. [2018-06-22 01:36:18,227 INFO ]: Finished removeUnreachable. Reduced from 78 states to 78 states and 263 transitions. [2018-06-22 01:36:18,227 INFO ]: Start accepts. Automaton has 78 states and 263 transitions. Word has length 13 [2018-06-22 01:36:18,227 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:18,227 INFO ]: Abstraction has 78 states and 263 transitions. [2018-06-22 01:36:18,227 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:36:18,227 INFO ]: Start isEmpty. Operand 78 states and 263 transitions. [2018-06-22 01:36:18,227 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 01:36:18,227 INFO ]: Found error trace [2018-06-22 01:36:18,227 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:18,227 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:18,227 INFO ]: Analyzing trace with hash -1937564142, now seen corresponding path program 1 times [2018-06-22 01:36:18,227 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:18,228 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:18,228 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:18,228 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:18,228 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:18,236 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:18,295 INFO ]: Checked inductivity of 21 backedges. 6 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:18,295 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:18,295 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:18,300 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:18,318 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:18,319 INFO ]: Computing forward predicates... [2018-06-22 01:36:18,819 INFO ]: Checked inductivity of 21 backedges. 4 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:18,838 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:18,838 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 14 [2018-06-22 01:36:18,838 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:18,838 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:18,838 INFO ]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:36:18,838 INFO ]: Start difference. First operand 78 states and 263 transitions. Second operand 14 states. [2018-06-22 01:36:19,224 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:19,224 INFO ]: Finished difference Result 164 states and 577 transitions. [2018-06-22 01:36:19,224 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 01:36:19,224 INFO ]: Start accepts. Automaton has 14 states. Word has length 13 [2018-06-22 01:36:19,224 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:19,226 INFO ]: With dead ends: 164 [2018-06-22 01:36:19,226 INFO ]: Without dead ends: 164 [2018-06-22 01:36:19,226 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=103, Invalid=277, Unknown=0, NotChecked=0, Total=380 [2018-06-22 01:36:19,226 INFO ]: Start minimizeSevpa. Operand 164 states. [2018-06-22 01:36:19,232 INFO ]: Finished minimizeSevpa. Reduced states from 164 to 68. [2018-06-22 01:36:19,232 INFO ]: Start removeUnreachable. Operand 68 states. [2018-06-22 01:36:19,233 INFO ]: Finished removeUnreachable. Reduced from 68 states to 68 states and 226 transitions. [2018-06-22 01:36:19,233 INFO ]: Start accepts. Automaton has 68 states and 226 transitions. Word has length 13 [2018-06-22 01:36:19,233 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:19,233 INFO ]: Abstraction has 68 states and 226 transitions. [2018-06-22 01:36:19,233 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:19,233 INFO ]: Start isEmpty. Operand 68 states and 226 transitions. [2018-06-22 01:36:19,233 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:36:19,234 INFO ]: Found error trace [2018-06-22 01:36:19,234 INFO ]: trace histogram [5, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:19,234 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:19,234 INFO ]: Analyzing trace with hash -1450969906, now seen corresponding path program 2 times [2018-06-22 01:36:19,234 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:19,234 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:19,234 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:19,234 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:19,234 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:19,245 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:19,344 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:19,344 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:19,344 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:19,350 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:36:19,370 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:36:19,371 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:19,373 INFO ]: Computing forward predicates... [2018-06-22 01:36:19,648 INFO ]: Checked inductivity of 28 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:36:19,666 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:19,666 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 15 [2018-06-22 01:36:19,666 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:36:19,667 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:36:19,667 INFO ]: CoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:36:19,667 INFO ]: Start difference. First operand 68 states and 226 transitions. Second operand 15 states. [2018-06-22 01:36:20,042 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:20,042 INFO ]: Finished difference Result 187 states and 678 transitions. [2018-06-22 01:36:20,042 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 01:36:20,042 INFO ]: Start accepts. Automaton has 15 states. Word has length 14 [2018-06-22 01:36:20,042 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:20,043 INFO ]: With dead ends: 187 [2018-06-22 01:36:20,043 INFO ]: Without dead ends: 182 [2018-06-22 01:36:20,044 INFO ]: 0 DeclaredPredicates, 33 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=187, Invalid=413, Unknown=0, NotChecked=0, Total=600 [2018-06-22 01:36:20,044 INFO ]: Start minimizeSevpa. Operand 182 states. [2018-06-22 01:36:20,047 INFO ]: Finished minimizeSevpa. Reduced states from 182 to 76. [2018-06-22 01:36:20,047 INFO ]: Start removeUnreachable. Operand 76 states. [2018-06-22 01:36:20,047 INFO ]: Finished removeUnreachable. Reduced from 76 states to 76 states and 254 transitions. [2018-06-22 01:36:20,047 INFO ]: Start accepts. Automaton has 76 states and 254 transitions. Word has length 14 [2018-06-22 01:36:20,048 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:20,048 INFO ]: Abstraction has 76 states and 254 transitions. [2018-06-22 01:36:20,048 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:36:20,048 INFO ]: Start isEmpty. Operand 76 states and 254 transitions. [2018-06-22 01:36:20,048 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:36:20,048 INFO ]: Found error trace [2018-06-22 01:36:20,048 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:20,048 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:20,048 INFO ]: Analyzing trace with hash 1774385878, now seen corresponding path program 1 times [2018-06-22 01:36:20,048 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:20,048 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:20,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:20,049 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:20,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:20,058 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:20,160 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:20,161 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:20,161 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:20,169 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:20,192 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:20,193 INFO ]: Computing forward predicates... [2018-06-22 01:36:20,217 INFO ]: Checked inductivity of 28 backedges. 15 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:36:20,248 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:20,248 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 5] total 13 [2018-06-22 01:36:20,248 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:36:20,248 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:36:20,248 INFO ]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:36:20,248 INFO ]: Start difference. First operand 76 states and 254 transitions. Second operand 13 states. [2018-06-22 01:36:20,669 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:20,669 INFO ]: Finished difference Result 229 states and 774 transitions. [2018-06-22 01:36:20,670 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 01:36:20,670 INFO ]: Start accepts. Automaton has 13 states. Word has length 14 [2018-06-22 01:36:20,670 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:20,671 INFO ]: With dead ends: 229 [2018-06-22 01:36:20,671 INFO ]: Without dead ends: 215 [2018-06-22 01:36:20,672 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=143, Invalid=507, Unknown=0, NotChecked=0, Total=650 [2018-06-22 01:36:20,672 INFO ]: Start minimizeSevpa. Operand 215 states. [2018-06-22 01:36:20,675 INFO ]: Finished minimizeSevpa. Reduced states from 215 to 76. [2018-06-22 01:36:20,675 INFO ]: Start removeUnreachable. Operand 76 states. [2018-06-22 01:36:20,676 INFO ]: Finished removeUnreachable. Reduced from 76 states to 76 states and 249 transitions. [2018-06-22 01:36:20,676 INFO ]: Start accepts. Automaton has 76 states and 249 transitions. Word has length 14 [2018-06-22 01:36:20,676 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:20,676 INFO ]: Abstraction has 76 states and 249 transitions. [2018-06-22 01:36:20,676 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:36:20,676 INFO ]: Start isEmpty. Operand 76 states and 249 transitions. [2018-06-22 01:36:20,677 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:36:20,677 INFO ]: Found error trace [2018-06-22 01:36:20,677 INFO ]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:20,677 INFO ]: === Iteration 32 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:20,677 INFO ]: Analyzing trace with hash -415349678, now seen corresponding path program 12 times [2018-06-22 01:36:20,677 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:20,677 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:20,681 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:20,681 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:20,681 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:20,688 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:20,736 INFO ]: Checked inductivity of 28 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:36:20,736 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:20,736 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:20,743 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:36:20,764 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-22 01:36:20,764 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:20,766 INFO ]: Computing forward predicates... [2018-06-22 01:36:20,822 INFO ]: Checked inductivity of 28 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:36:20,846 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:20,846 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 01:36:20,846 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:20,846 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:20,846 INFO ]: CoverageRelationStatistics Valid=33, Invalid=149, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:36:20,846 INFO ]: Start difference. First operand 76 states and 249 transitions. Second operand 14 states. [2018-06-22 01:36:21,284 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:21,284 INFO ]: Finished difference Result 200 states and 659 transitions. [2018-06-22 01:36:21,285 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-22 01:36:21,285 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-22 01:36:21,285 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:21,286 INFO ]: With dead ends: 200 [2018-06-22 01:36:21,286 INFO ]: Without dead ends: 200 [2018-06-22 01:36:21,286 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 193 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=189, Invalid=867, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 01:36:21,287 INFO ]: Start minimizeSevpa. Operand 200 states. [2018-06-22 01:36:21,290 INFO ]: Finished minimizeSevpa. Reduced states from 200 to 103. [2018-06-22 01:36:21,291 INFO ]: Start removeUnreachable. Operand 103 states. [2018-06-22 01:36:21,292 INFO ]: Finished removeUnreachable. Reduced from 103 states to 103 states and 323 transitions. [2018-06-22 01:36:21,292 INFO ]: Start accepts. Automaton has 103 states and 323 transitions. Word has length 14 [2018-06-22 01:36:21,292 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:21,292 INFO ]: Abstraction has 103 states and 323 transitions. [2018-06-22 01:36:21,292 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:21,292 INFO ]: Start isEmpty. Operand 103 states and 323 transitions. [2018-06-22 01:36:21,293 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:36:21,293 INFO ]: Found error trace [2018-06-22 01:36:21,293 INFO ]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:21,293 INFO ]: === Iteration 33 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:21,293 INFO ]: Analyzing trace with hash -747817238, now seen corresponding path program 13 times [2018-06-22 01:36:21,293 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:21,293 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:21,294 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:21,294 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:36:21,294 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:21,302 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:21,379 INFO ]: Checked inductivity of 28 backedges. 7 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:21,379 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:21,379 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:21,385 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:21,404 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:21,406 INFO ]: Computing forward predicates... [2018-06-22 01:36:22,846 INFO ]: Checked inductivity of 28 backedges. 11 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:22,867 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:22,867 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2018-06-22 01:36:22,867 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:36:22,867 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:36:22,867 INFO ]: CoverageRelationStatistics Valid=45, Invalid=134, Unknown=3, NotChecked=0, Total=182 [2018-06-22 01:36:22,867 INFO ]: Start difference. First operand 103 states and 323 transitions. Second operand 14 states. [2018-06-22 01:36:25,817 WARN ]: Spent 315.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 47 [2018-06-22 01:36:26,525 WARN ]: Spent 522.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 55 [2018-06-22 01:36:26,526 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:36:26,526 INFO ]: Finished difference Result 154 states and 414 transitions. [2018-06-22 01:36:26,526 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-22 01:36:26,526 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-22 01:36:26,526 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:36:26,527 INFO ]: With dead ends: 154 [2018-06-22 01:36:26,527 INFO ]: Without dead ends: 154 [2018-06-22 01:36:26,528 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 10 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=183, Invalid=464, Unknown=3, NotChecked=0, Total=650 [2018-06-22 01:36:26,528 INFO ]: Start minimizeSevpa. Operand 154 states. [2018-06-22 01:36:26,534 INFO ]: Finished minimizeSevpa. Reduced states from 154 to 138. [2018-06-22 01:36:26,534 INFO ]: Start removeUnreachable. Operand 138 states. [2018-06-22 01:36:26,534 INFO ]: Finished removeUnreachable. Reduced from 138 states to 138 states and 398 transitions. [2018-06-22 01:36:26,534 INFO ]: Start accepts. Automaton has 138 states and 398 transitions. Word has length 14 [2018-06-22 01:36:26,535 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:36:26,535 INFO ]: Abstraction has 138 states and 398 transitions. [2018-06-22 01:36:26,535 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:36:26,535 INFO ]: Start isEmpty. Operand 138 states and 398 transitions. [2018-06-22 01:36:26,535 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:36:26,535 INFO ]: Found error trace [2018-06-22 01:36:26,535 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:36:26,535 INFO ]: === Iteration 34 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:36:26,536 INFO ]: Analyzing trace with hash -758899490, now seen corresponding path program 14 times [2018-06-22 01:36:26,536 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:36:26,536 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:36:26,536 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:26,536 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:36:26,536 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:36:26,546 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:26,656 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:26,656 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:36:26,656 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:36:26,662 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:36:26,683 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:36:26,684 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:36:26,686 INFO ]: Computing forward predicates... [2018-06-22 01:36:27,648 WARN ]: Spent 249.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 73 [2018-06-22 01:36:30,034 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:36:30,053 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:36:30,053 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 01:36:30,053 INFO ]: Interpolant automaton has 17 states [2018-06-22 01:36:30,053 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 01:36:30,054 INFO ]: CoverageRelationStatistics Valid=44, Invalid=227, Unknown=1, NotChecked=0, Total=272 [2018-06-22 01:36:30,054 INFO ]: Start difference. First operand 138 states and 398 transitions. Second operand 17 states. Received shutdown request... [2018-06-22 01:36:39,143 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-06-22 01:36:39,143 WARN ]: Verification canceled [2018-06-22 01:36:39,147 WARN ]: Timeout [2018-06-22 01:36:39,148 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:36:39 BoogieIcfgContainer [2018-06-22 01:36:39,148 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:36:39,148 INFO ]: Toolchain (without parser) took 69778.77 ms. Allocated memory was 309.3 MB in the beginning and 467.1 MB in the end (delta: 157.8 MB). Free memory was 261.7 MB in the beginning and 252.1 MB in the end (delta: 9.6 MB). Peak memory consumption was 167.4 MB. Max. memory is 3.6 GB. [2018-06-22 01:36:39,149 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:36:39,149 INFO ]: ChcToBoogie took 84.54 ms. Allocated memory is still 309.3 MB. Free memory was 260.7 MB in the beginning and 258.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:36:39,150 INFO ]: Boogie Preprocessor took 47.26 ms. Allocated memory is still 309.3 MB. Free memory was 258.7 MB in the beginning and 257.7 MB in the end (delta: 1.0 MB). Peak memory consumption was 1.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:36:39,151 INFO ]: RCFGBuilder took 523.84 ms. Allocated memory is still 309.3 MB. Free memory was 257.7 MB in the beginning and 240.7 MB in the end (delta: 17.0 MB). Peak memory consumption was 17.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:36:39,151 INFO ]: TraceAbstraction took 69114.58 ms. Allocated memory was 309.3 MB in the beginning and 467.1 MB in the end (delta: 157.8 MB). Free memory was 240.7 MB in the beginning and 252.1 MB in the end (delta: -11.4 MB). Peak memory consumption was 146.4 MB. Max. memory is 3.6 GB. [2018-06-22 01:36:39,153 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 84.54 ms. Allocated memory is still 309.3 MB. Free memory was 260.7 MB in the beginning and 258.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 47.26 ms. Allocated memory is still 309.3 MB. Free memory was 258.7 MB in the beginning and 257.7 MB in the end (delta: 1.0 MB). Peak memory consumption was 1.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 523.84 ms. Allocated memory is still 309.3 MB. Free memory was 257.7 MB in the beginning and 240.7 MB in the end (delta: 17.0 MB). Peak memory consumption was 17.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 69114.58 ms. Allocated memory was 309.3 MB in the beginning and 467.1 MB in the end (delta: 157.8 MB). Free memory was 240.7 MB in the beginning and 252.1 MB in the end (delta: -11.4 MB). Peak memory consumption was 146.4 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 (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (138states) and interpolant automaton (currently 21 states, 17 states before enhancement), while ReachableStatesComputation was computing reachable states (165 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 12 locations, 1 error locations. TIMEOUT Result, 69.0s OverallTime, 34 OverallIterations, 5 TraceHistogramMax, 51.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 283 SDtfs, 147 SDslu, 1101 SDs, 0 SdLazy, 3946 SolverSat, 2009 SolverUnsat, 20 SolverUnknown, 0 SolverNotchecked, 34.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 767 GetRequests, 264 SyntacticMatches, 19 SemanticMatches, 484 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2294 ImplicationChecksByTransitivity, 29.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=138occurred in iteration=33, 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.1s AutomataMinimizationTime, 33 MinimizatonAttempts, 1304 StatesRemovedByMinimization, 29 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 15.2s InterpolantComputationTime, 692 NumberOfCodeBlocks, 692 NumberOfCodeBlocksAsserted, 95 NumberOfCheckSat, 629 ConstructedInterpolants, 46 QuantifiedInterpolants, 43068 SizeOfPredicates, 38 NumberOfNonLiveVariables, 4103 ConjunctsInSsa, 826 ConjunctsInUnsatCore, 63 InterpolantComputations, 5 PerfectInterpolantSequences, 143/749 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/025-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-36-39-165.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/025-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-36-39-165.csv Completed graceful shutdown