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_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/split.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:37:32,990 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:37:32,992 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:37:33,007 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:37:33,008 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:37:33,009 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:37:33,010 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:37:33,014 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:37:33,015 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:37:33,017 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:37:33,018 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:37:33,018 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:37:33,019 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:37:33,022 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:37:33,023 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:37:33,024 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:37:33,025 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:37:33,035 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:37:33,036 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:37:33,037 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:37:33,038 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:37:33,043 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:37:33,043 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:37:33,043 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:37:33,044 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:37:33,049 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:37:33,050 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:37:33,051 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:37:33,052 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:37:33,052 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:37:33,052 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:37:33,055 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:37:33,055 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:37:33,056 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:37:33,057 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:37:33,057 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:37:33,077 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:37:33,077 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:37:33,077 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:37:33,078 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:37:33,079 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:37:33,079 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:37:33,079 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:37:33,079 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:37:33,079 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:37:33,080 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:37:33,081 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:37:33,081 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:37:33,081 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:37:33,081 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:37:33,081 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:37:33,082 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:37:33,082 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:37:33,082 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:37:33,082 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:37:33,083 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:37:33,084 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:37:33,127 INFO ]: Repository-Root is: /tmp [2018-06-22 15:37:33,144 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:37:33,150 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:37:33,152 INFO ]: Initializing SmtParser... [2018-06-22 15:37:33,152 INFO ]: SmtParser initialized [2018-06-22 15:37:33,153 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/split.c.smt2 [2018-06-22 15:37:33,154 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 15:37:33,252 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/split.c.smt2 unknown [2018-06-22 15:37:33,551 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/split.c.smt2 [2018-06-22 15:37:33,556 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:37:33,562 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:37:33,562 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:37:33,562 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:37:33,562 INFO ]: ChcToBoogie initialized [2018-06-22 15:37:33,566 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,623 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33 Unit [2018-06-22 15:37:33,624 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:37:33,624 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:37:33,625 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:37:33,625 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:37:33,647 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,647 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,655 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,656 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,661 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,662 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,663 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (1/1) ... [2018-06-22 15:37:33,665 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:37:33,666 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:37:33,666 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:37:33,666 INFO ]: RCFGBuilder initialized [2018-06-22 15:37:33,667 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (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 15:37:33,677 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:37:33,677 INFO ]: Found specification of procedure False [2018-06-22 15:37:33,677 INFO ]: Found implementation of procedure False [2018-06-22 15:37:33,677 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:37:33,677 INFO ]: Found specification of procedure state [2018-06-22 15:37:33,677 INFO ]: Found implementation of procedure state [2018-06-22 15:37:33,677 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:37:33,677 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:37:33,677 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 15:37:33,957 INFO ]: Using library mode [2018-06-22 15:37:33,958 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:37:33 BoogieIcfgContainer [2018-06-22 15:37:33,958 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:37:33,959 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:37:33,959 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:37:33,963 INFO ]: TraceAbstraction initialized [2018-06-22 15:37:33,963 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:37:33" (1/3) ... [2018-06-22 15:37:33,970 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@795bfb38 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:37:33, skipping insertion in model container [2018-06-22 15:37:33,970 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:37:33" (2/3) ... [2018-06-22 15:37:33,971 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@795bfb38 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:37:33, skipping insertion in model container [2018-06-22 15:37:33,971 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:37:33" (3/3) ... [2018-06-22 15:37:33,973 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:37:33,987 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:37:34,007 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:37:34,056 INFO ]: Using default assertion order modulation [2018-06-22 15:37:34,056 INFO ]: Interprodecural is true [2018-06-22 15:37:34,056 INFO ]: Hoare is false [2018-06-22 15:37:34,056 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:37:34,056 INFO ]: Backedges is TWOTRACK [2018-06-22 15:37:34,056 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:37:34,056 INFO ]: Difference is false [2018-06-22 15:37:34,056 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:37:34,056 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:37:34,072 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:37:34,085 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:37:34,086 INFO ]: Found error trace [2018-06-22 15:37:34,087 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:34,087 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:34,095 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:37:34,097 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:34,098 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:34,145 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:34,145 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:34,145 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:34,179 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:34,330 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:37:34,333 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:37:34,334 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:37:34,336 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:37:34,354 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:37:34,354 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:37:34,357 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:37:34,492 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:34,492 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:37:34,492 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:37:34,494 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:37:34,494 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:34,505 INFO ]: With dead ends: 13 [2018-06-22 15:37:34,506 INFO ]: Without dead ends: 13 [2018-06-22 15:37:34,508 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 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 15:37:34,529 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:37:34,553 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:37:34,555 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:37:34,556 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:37:34,558 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:37:34,558 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:34,558 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:37:34,558 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:37:34,558 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:37:34,560 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:37:34,560 INFO ]: Found error trace [2018-06-22 15:37:34,560 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:34,560 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:34,561 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:37:34,561 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:34,561 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:34,562 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:34,562 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:34,562 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:34,628 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:34,830 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:37:34,831 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:34,831 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:37:34,848 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:34,902 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:34,911 INFO ]: Computing forward predicates... [2018-06-22 15:37:35,245 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:37:35,271 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:35,271 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:37:35,272 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:37:35,272 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:37:35,272 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:37:35,272 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:37:35,397 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:35,398 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:37:35,399 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:37:35,399 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:37:35,399 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:35,399 INFO ]: With dead ends: 15 [2018-06-22 15:37:35,399 INFO ]: Without dead ends: 15 [2018-06-22 15:37:35,400 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:37:35,400 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:37:35,404 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:37:35,404 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:37:35,405 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:37:35,405 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:37:35,405 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:35,405 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:37:35,405 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:37:35,405 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:37:35,406 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:37:35,406 INFO ]: Found error trace [2018-06-22 15:37:35,406 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:35,406 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:35,406 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:37:35,406 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:35,406 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:35,407 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:35,407 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:35,407 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:35,467 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:35,962 WARN ]: Spent 249.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:37:36,160 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:37:36,160 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:36,160 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) [2018-06-22 15:37:36,179 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:37:36,237 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:37:36,237 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:36,241 INFO ]: Computing forward predicates... [2018-06-22 15:37:36,522 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:37:36,541 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:36,542 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 15:37:36,542 INFO ]: Interpolant automaton has 8 states [2018-06-22 15:37:36,542 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 15:37:36,542 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 15:37:36,542 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 8 states. [2018-06-22 15:37:36,697 WARN ]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 15:37:37,205 WARN ]: Spent 396.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 18 [2018-06-22 15:37:37,220 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:37,220 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:37:37,221 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:37:37,221 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-22 15:37:37,221 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:37,221 INFO ]: With dead ends: 17 [2018-06-22 15:37:37,221 INFO ]: Without dead ends: 17 [2018-06-22 15:37:37,222 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=31, Invalid=59, Unknown=0, NotChecked=0, Total=90 [2018-06-22 15:37:37,222 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:37:37,225 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:37:37,225 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:37:37,225 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:37:37,226 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:37:37,226 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:37,226 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:37:37,226 INFO ]: Interpolant automaton has 8 states. [2018-06-22 15:37:37,226 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:37:37,226 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:37:37,226 INFO ]: Found error trace [2018-06-22 15:37:37,226 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:37,227 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:37,227 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:37:37,227 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:37,227 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:37,228 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:37,228 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:37,228 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:37,260 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:37,607 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:37:37,607 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:37,607 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 15:37:37,616 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:37:37,677 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:37:37,677 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:37,682 INFO ]: Computing forward predicates... [2018-06-22 15:37:38,074 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:37:38,106 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:38,107 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-22 15:37:38,107 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:37:38,107 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:37:38,108 INFO ]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:37:38,108 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-22 15:37:38,623 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 13 [2018-06-22 15:37:38,647 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:38,647 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:37:38,648 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:37:38,648 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 15:37:38,648 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:38,649 INFO ]: With dead ends: 19 [2018-06-22 15:37:38,649 INFO ]: Without dead ends: 19 [2018-06-22 15:37:38,649 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=64, Invalid=242, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:37:38,649 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:37:38,652 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:37:38,652 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:37:38,653 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:37:38,653 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:37:38,653 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:38,653 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:37:38,653 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:37:38,653 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:37:38,654 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:37:38,654 INFO ]: Found error trace [2018-06-22 15:37:38,654 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:38,654 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:38,654 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:37:38,654 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:38,654 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:38,655 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:38,655 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:38,655 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:38,695 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:38,896 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:37:38,896 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:38,896 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 15:37:38,909 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:37:38,965 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:37:38,965 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:38,970 INFO ]: Computing forward predicates... [2018-06-22 15:37:39,150 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:37:39,170 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:39,170 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 15 [2018-06-22 15:37:39,170 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:37:39,170 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:37:39,170 INFO ]: CoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:37:39,171 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 15 states. [2018-06-22 15:37:39,573 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:39,573 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:37:39,577 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:37:39,577 INFO ]: Start accepts. Automaton has 15 states. Word has length 25 [2018-06-22 15:37:39,577 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:39,578 INFO ]: With dead ends: 21 [2018-06-22 15:37:39,578 INFO ]: Without dead ends: 21 [2018-06-22 15:37:39,578 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=95, Invalid=325, Unknown=0, NotChecked=0, Total=420 [2018-06-22 15:37:39,578 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:37:39,581 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:37:39,581 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:37:39,585 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:37:39,585 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:37:39,585 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:39,585 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:37:39,585 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:37:39,585 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:37:39,586 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:37:39,586 INFO ]: Found error trace [2018-06-22 15:37:39,586 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:39,586 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:39,586 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:37:39,586 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:39,586 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:39,587 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:39,587 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:39,587 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:39,633 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:40,017 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:37:40,017 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:40,017 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 15:37:40,028 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:37:40,091 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:37:40,091 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:40,095 INFO ]: Computing forward predicates... [2018-06-22 15:37:40,683 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:37:40,703 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:40,703 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2018-06-22 15:37:40,703 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:37:40,704 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:37:40,704 INFO ]: CoverageRelationStatistics Valid=84, Invalid=516, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:37:40,704 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 25 states. [2018-06-22 15:37:41,339 WARN ]: Spent 592.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 61 [2018-06-22 15:37:41,491 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 31 [2018-06-22 15:37:41,656 WARN ]: Spent 129.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 36 [2018-06-22 15:37:41,846 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 39 [2018-06-22 15:37:42,092 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 48 [2018-06-22 15:37:42,147 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:42,147 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:37:42,151 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:37:42,151 INFO ]: Start accepts. Automaton has 25 states. Word has length 29 [2018-06-22 15:37:42,151 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:42,151 INFO ]: With dead ends: 23 [2018-06-22 15:37:42,151 INFO ]: Without dead ends: 23 [2018-06-22 15:37:42,152 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=183, Invalid=809, Unknown=0, NotChecked=0, Total=992 [2018-06-22 15:37:42,152 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:37:42,156 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:37:42,156 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:37:42,157 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:37:42,157 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:37:42,157 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:42,157 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:37:42,157 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:37:42,157 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:37:42,158 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:37:42,158 INFO ]: Found error trace [2018-06-22 15:37:42,158 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:42,158 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:42,158 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:37:42,158 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:42,158 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:42,159 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:42,160 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:42,160 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:42,200 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:42,771 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:37:42,771 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:42,771 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 15:37:42,779 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:37:42,849 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:37:42,852 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:42,858 INFO ]: Computing forward predicates... [2018-06-22 15:37:44,189 WARN ]: Spent 415.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 15:37:44,836 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:37:44,871 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:44,871 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 29 [2018-06-22 15:37:44,872 INFO ]: Interpolant automaton has 29 states [2018-06-22 15:37:44,872 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 15:37:44,872 INFO ]: CoverageRelationStatistics Valid=101, Invalid=711, Unknown=0, NotChecked=0, Total=812 [2018-06-22 15:37:44,873 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 29 states. [2018-06-22 15:37:45,664 WARN ]: Spent 729.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 76 [2018-06-22 15:37:45,824 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 34 [2018-06-22 15:37:46,041 WARN ]: Spent 189.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 38 [2018-06-22 15:37:46,331 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 44 [2018-06-22 15:37:46,578 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 27 [2018-06-22 15:37:46,733 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 31 [2018-06-22 15:37:47,290 WARN ]: Spent 422.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 66 [2018-06-22 15:37:47,323 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:47,323 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:37:47,324 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:37:47,324 INFO ]: Start accepts. Automaton has 29 states. Word has length 33 [2018-06-22 15:37:47,324 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:47,325 INFO ]: With dead ends: 25 [2018-06-22 15:37:47,325 INFO ]: Without dead ends: 25 [2018-06-22 15:37:47,326 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=234, Invalid=1098, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:37:47,326 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:37:47,331 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:37:47,331 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:37:47,332 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:37:47,332 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:37:47,332 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:47,332 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:37:47,332 INFO ]: Interpolant automaton has 29 states. [2018-06-22 15:37:47,332 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:37:47,333 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:37:47,333 INFO ]: Found error trace [2018-06-22 15:37:47,333 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:47,333 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:47,333 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:37:47,333 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:47,333 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:47,334 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:47,334 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:37:47,334 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:47,404 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:48,186 WARN ]: Spent 501.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:37:48,642 WARN ]: Spent 381.00 ms on a formula simplification that was a NOOP. DAG size: 30 [2018-06-22 15:37:48,803 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2018-06-22 15:37:49,173 WARN ]: Spent 153.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:37:49,386 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:37:49,386 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:49,386 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 15:37:49,393 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:49,475 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:49,482 INFO ]: Computing forward predicates... [2018-06-22 15:37:50,346 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 18 [2018-06-22 15:37:50,788 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 25 [2018-06-22 15:37:51,234 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:37:51,255 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:51,255 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 28 [2018-06-22 15:37:51,255 INFO ]: Interpolant automaton has 28 states [2018-06-22 15:37:51,255 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 15:37:51,259 INFO ]: CoverageRelationStatistics Valid=83, Invalid=673, Unknown=0, NotChecked=0, Total=756 [2018-06-22 15:37:51,259 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 28 states. [2018-06-22 15:37:51,779 WARN ]: Spent 455.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 72 [2018-06-22 15:37:52,092 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 28 [2018-06-22 15:37:52,360 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 35 [2018-06-22 15:37:52,674 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 35 [2018-06-22 15:37:52,909 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 42 [2018-06-22 15:37:53,178 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 39 [2018-06-22 15:37:53,733 WARN ]: Spent 414.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 63 [2018-06-22 15:37:53,782 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:37:53,782 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:37:53,783 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:37:53,783 INFO ]: Start accepts. Automaton has 28 states. Word has length 37 [2018-06-22 15:37:53,783 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:37:53,784 INFO ]: With dead ends: 27 [2018-06-22 15:37:53,784 INFO ]: Without dead ends: 27 [2018-06-22 15:37:53,784 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=231, Invalid=1101, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:37:53,784 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:37:53,788 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:37:53,788 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:37:53,788 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:37:53,789 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:37:53,789 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:37:53,789 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:37:53,789 INFO ]: Interpolant automaton has 28 states. [2018-06-22 15:37:53,789 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:37:53,790 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:37:53,790 INFO ]: Found error trace [2018-06-22 15:37:53,790 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:37:53,790 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:37:53,790 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-22 15:37:53,790 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:37:53,790 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:37:53,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:53,791 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:37:53,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:37:53,856 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:54,269 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 21 [2018-06-22 15:37:54,578 WARN ]: Spent 159.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2018-06-22 15:37:55,038 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:37:55,038 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:37:55,038 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 15:37:55,043 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:37:55,095 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:37:55,095 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:37:55,101 INFO ]: Computing forward predicates... [2018-06-22 15:37:55,422 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 26 [2018-06-22 15:37:55,747 WARN ]: Spent 155.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-22 15:37:55,916 WARN ]: Spent 135.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 24 [2018-06-22 15:37:56,804 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:37:56,824 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:37:56,824 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 37 [2018-06-22 15:37:56,825 INFO ]: Interpolant automaton has 37 states [2018-06-22 15:37:56,825 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 15:37:56,825 INFO ]: CoverageRelationStatistics Valid=112, Invalid=1220, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:37:56,825 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 37 states. [2018-06-22 15:37:57,737 WARN ]: Spent 829.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 106 [2018-06-22 15:37:58,125 WARN ]: Spent 300.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 35 [2018-06-22 15:37:58,551 WARN ]: Spent 361.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 51 [2018-06-22 15:37:58,890 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 49 [2018-06-22 15:37:59,144 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 38 [2018-06-22 15:37:59,496 WARN ]: Spent 296.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 51 [2018-06-22 15:37:59,867 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 54 [2018-06-22 15:38:00,390 WARN ]: Spent 342.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 54 [2018-06-22 15:38:01,247 WARN ]: Spent 665.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 98 [2018-06-22 15:38:01,294 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:38:01,294 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:38:01,295 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:38:01,295 INFO ]: Start accepts. Automaton has 37 states. Word has length 41 [2018-06-22 15:38:01,295 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:38:01,296 INFO ]: With dead ends: 29 [2018-06-22 15:38:01,296 INFO ]: Without dead ends: 29 [2018-06-22 15:38:01,296 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 169 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=323, Invalid=1839, Unknown=0, NotChecked=0, Total=2162 [2018-06-22 15:38:01,296 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:38:01,300 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:38:01,300 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:38:01,301 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:38:01,301 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:38:01,301 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:38:01,301 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:38:01,301 INFO ]: Interpolant automaton has 37 states. [2018-06-22 15:38:01,301 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:38:01,302 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:38:01,302 INFO ]: Found error trace [2018-06-22 15:38:01,302 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:38:01,302 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:38:01,302 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-22 15:38:01,302 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:38:01,302 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:38:01,303 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:01,303 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:38:01,303 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:01,355 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:02,176 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:38:02,177 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:38:02,177 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 15:38:02,183 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:38:02,257 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:38:02,257 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:02,264 INFO ]: Computing forward predicates... [2018-06-22 15:38:03,227 WARN ]: Spent 794.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 38 [2018-06-22 15:38:03,902 WARN ]: Spent 552.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 42 [2018-06-22 15:38:04,104 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-22 15:38:05,398 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:38:05,428 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:38:05,428 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 41 [2018-06-22 15:38:05,428 INFO ]: Interpolant automaton has 41 states [2018-06-22 15:38:05,428 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 15:38:05,429 INFO ]: CoverageRelationStatistics Valid=122, Invalid=1518, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:38:05,429 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 41 states. [2018-06-22 15:38:07,196 WARN ]: Spent 1.59 s on a formula simplification. DAG size of input: 147 DAG size of output: 109 [2018-06-22 15:38:07,494 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 36 [2018-06-22 15:38:07,773 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 35 [2018-06-22 15:38:08,175 WARN ]: Spent 340.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 47 [2018-06-22 15:38:08,660 WARN ]: Spent 349.00 ms on a formula simplification. DAG size of input: 139 DAG size of output: 28 [2018-06-22 15:38:09,102 WARN ]: Spent 346.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 42 [2018-06-22 15:38:09,500 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 43 [2018-06-22 15:38:09,940 WARN ]: Spent 356.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 47 [2018-06-22 15:38:10,311 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 37 [2018-06-22 15:38:11,210 WARN ]: Spent 809.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 97 [2018-06-22 15:38:11,272 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:38:11,273 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:38:11,273 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:38:11,273 INFO ]: Start accepts. Automaton has 41 states. Word has length 45 [2018-06-22 15:38:11,273 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:38:11,275 INFO ]: With dead ends: 31 [2018-06-22 15:38:11,275 INFO ]: Without dead ends: 31 [2018-06-22 15:38:11,276 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 188 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=377, Invalid=2275, Unknown=0, NotChecked=0, Total=2652 [2018-06-22 15:38:11,276 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:38:11,280 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:38:11,280 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:38:11,282 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:38:11,282 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:38:11,282 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:38:11,282 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:38:11,282 INFO ]: Interpolant automaton has 41 states. [2018-06-22 15:38:11,283 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:38:11,283 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:38:11,283 INFO ]: Found error trace [2018-06-22 15:38:11,283 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:38:11,284 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:38:11,284 INFO ]: Analyzing trace with hash 352352522, now seen corresponding path program 10 times [2018-06-22 15:38:11,284 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:38:11,284 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:38:11,284 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:11,284 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:38:11,284 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:11,342 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:12,218 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:38:12,218 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:38:12,218 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 15:38:12,224 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:38:12,301 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:38:12,301 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:12,316 INFO ]: Computing forward predicates... [2018-06-22 15:38:12,879 WARN ]: Spent 358.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 24 [2018-06-22 15:38:13,140 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 29 [2018-06-22 15:38:13,369 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 36 [2018-06-22 15:38:13,606 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 37 [2018-06-22 15:38:13,755 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 27 [2018-06-22 15:38:16,258 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:38:16,278 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:38:16,278 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 45 [2018-06-22 15:38:16,279 INFO ]: Interpolant automaton has 45 states [2018-06-22 15:38:16,281 INFO ]: Constructing interpolant automaton starting with 45 interpolants. [2018-06-22 15:38:16,281 INFO ]: CoverageRelationStatistics Valid=125, Invalid=1855, Unknown=0, NotChecked=0, Total=1980 [2018-06-22 15:38:16,281 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 45 states. [2018-06-22 15:38:17,290 WARN ]: Spent 930.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 101 [2018-06-22 15:38:17,559 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 34 [2018-06-22 15:38:17,830 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 39 [2018-06-22 15:38:18,113 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 46 [2018-06-22 15:38:18,507 WARN ]: Spent 263.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 36 [2018-06-22 15:38:18,884 WARN ]: Spent 305.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 38 [2018-06-22 15:38:19,277 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 38 [2018-06-22 15:38:19,850 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 42 [2018-06-22 15:38:20,237 WARN ]: Spent 309.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 36 [2018-06-22 15:38:20,600 WARN ]: Spent 263.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 33 [2018-06-22 15:38:21,134 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 153 DAG size of output: 70 [2018-06-22 15:38:22,036 WARN ]: Spent 826.00 ms on a formula simplification. DAG size of input: 154 DAG size of output: 100 [2018-06-22 15:38:22,094 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:38:22,094 INFO ]: Finished difference Result 35 states and 36 transitions. [2018-06-22 15:38:22,095 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 15:38:22,095 INFO ]: Start accepts. Automaton has 45 states. Word has length 49 [2018-06-22 15:38:22,095 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:38:22,096 INFO ]: With dead ends: 35 [2018-06-22 15:38:22,096 INFO ]: Without dead ends: 35 [2018-06-22 15:38:22,097 INFO ]: 0 DeclaredPredicates, 85 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 290 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=448, Invalid=2858, Unknown=0, NotChecked=0, Total=3306 [2018-06-22 15:38:22,097 INFO ]: Start minimizeSevpa. Operand 35 states. [2018-06-22 15:38:22,101 INFO ]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-06-22 15:38:22,101 INFO ]: Start removeUnreachable. Operand 35 states. [2018-06-22 15:38:22,102 INFO ]: Finished removeUnreachable. Reduced from 35 states to 35 states and 36 transitions. [2018-06-22 15:38:22,102 INFO ]: Start accepts. Automaton has 35 states and 36 transitions. Word has length 49 [2018-06-22 15:38:22,102 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:38:22,102 INFO ]: Abstraction has 35 states and 36 transitions. [2018-06-22 15:38:22,102 INFO ]: Interpolant automaton has 45 states. [2018-06-22 15:38:22,102 INFO ]: Start isEmpty. Operand 35 states and 36 transitions. [2018-06-22 15:38:22,105 INFO ]: Finished isEmpty. Found accepting run of length 58 [2018-06-22 15:38:22,105 INFO ]: Found error trace [2018-06-22 15:38:22,105 INFO ]: trace histogram [13, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:38:22,105 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:38:22,105 INFO ]: Analyzing trace with hash -1286307758, now seen corresponding path program 11 times [2018-06-22 15:38:22,105 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:38:22,105 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:38:22,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:22,106 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:38:22,106 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:38:22,228 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:23,240 WARN ]: Spent 679.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 15:38:23,435 WARN ]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 37 [2018-06-22 15:38:23,943 WARN ]: Spent 237.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 42 [2018-06-22 15:38:24,155 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 40 [2018-06-22 15:38:24,325 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 52 [2018-06-22 15:38:25,725 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 27 [2018-06-22 15:38:25,888 INFO ]: Checked inductivity of 300 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2018-06-22 15:38:25,888 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:38:25,888 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 15:38:25,894 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:38:25,994 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 13 check-sat command(s) [2018-06-22 15:38:25,994 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:38:26,003 INFO ]: Computing forward predicates... [2018-06-22 15:38:26,621 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 31 [2018-06-22 15:38:29,082 INFO ]: Checked inductivity of 300 backedges. 0 proven. 222 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2018-06-22 15:38:29,102 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:38:29,102 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 53 [2018-06-22 15:38:29,103 INFO ]: Interpolant automaton has 53 states [2018-06-22 15:38:29,103 INFO ]: Constructing interpolant automaton starting with 53 interpolants. [2018-06-22 15:38:29,103 INFO ]: CoverageRelationStatistics Valid=174, Invalid=2582, Unknown=0, NotChecked=0, Total=2756 [2018-06-22 15:38:29,104 INFO ]: Start difference. First operand 35 states and 36 transitions. Second operand 53 states. [2018-06-22 15:38:30,944 WARN ]: Spent 1.74 s on a formula simplification. DAG size of input: 190 DAG size of output: 123 [2018-06-22 15:38:31,330 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 188 DAG size of output: 33 [2018-06-22 15:38:33,131 WARN ]: Spent 277.00 ms on a formula simplification. DAG size of input: 190 DAG size of output: 38 [2018-06-22 15:38:33,592 WARN ]: Spent 332.00 ms on a formula simplification. DAG size of input: 184 DAG size of output: 53 [2018-06-22 15:38:34,027 WARN ]: Spent 284.00 ms on a formula simplification. DAG size of input: 179 DAG size of output: 47 [2018-06-22 15:38:34,442 WARN ]: Spent 322.00 ms on a formula simplification. DAG size of input: 192 DAG size of output: 47 [2018-06-22 15:38:34,871 WARN ]: Spent 332.00 ms on a formula simplification. DAG size of input: 192 DAG size of output: 47 [2018-06-22 15:38:35,421 WARN ]: Spent 451.00 ms on a formula simplification. DAG size of input: 196 DAG size of output: 56 [2018-06-22 15:38:35,881 WARN ]: Spent 370.00 ms on a formula simplification. DAG size of input: 199 DAG size of output: 50 [2018-06-22 15:38:36,411 WARN ]: Spent 434.00 ms on a formula simplification. DAG size of input: 202 DAG size of output: 58 [2018-06-22 15:38:37,023 WARN ]: Spent 479.00 ms on a formula simplification. DAG size of input: 193 DAG size of output: 69 Received shutdown request... [2018-06-22 15:38:37,543 WARN ]: Removed 6 from assertion stack [2018-06-22 15:38:37,543 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 15:38:37,543 WARN ]: Verification canceled [2018-06-22 15:38:37,547 WARN ]: Timeout [2018-06-22 15:38:37,547 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:38:37 BoogieIcfgContainer [2018-06-22 15:38:37,547 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:38:37,548 INFO ]: Toolchain (without parser) took 63991.59 ms. Allocated memory was 309.3 MB in the beginning and 756.0 MB in the end (delta: 446.7 MB). Free memory was 261.9 MB in the beginning and 368.6 MB in the end (delta: -106.8 MB). Peak memory consumption was 339.9 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:37,548 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 275.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:38:37,548 INFO ]: ChcToBoogie took 61.82 ms. Allocated memory is still 309.3 MB. Free memory was 261.9 MB in the beginning and 259.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:37,549 INFO ]: Boogie Preprocessor took 40.97 ms. Allocated memory is still 309.3 MB. Free memory was 259.9 MB in the beginning and 257.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:37,549 INFO ]: RCFGBuilder took 292.25 ms. Allocated memory is still 309.3 MB. Free memory was 257.9 MB in the beginning and 248.9 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:37,550 INFO ]: TraceAbstraction took 63587.66 ms. Allocated memory was 309.3 MB in the beginning and 756.0 MB in the end (delta: 446.7 MB). Free memory was 248.9 MB in the beginning and 368.6 MB in the end (delta: -119.7 MB). Peak memory consumption was 327.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:38:37,552 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 275.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 61.82 ms. Allocated memory is still 309.3 MB. Free memory was 261.9 MB in the beginning and 259.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 40.97 ms. Allocated memory is still 309.3 MB. Free memory was 259.9 MB in the beginning and 257.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 292.25 ms. Allocated memory is still 309.3 MB. Free memory was 257.9 MB in the beginning and 248.9 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63587.66 ms. Allocated memory was 309.3 MB in the beginning and 756.0 MB in the end (delta: 446.7 MB). Free memory was 248.9 MB in the beginning and 368.6 MB in the end (delta: -119.7 MB). Peak memory consumption was 327.0 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 (35states) and interpolant automaton (currently 15 states, 53 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 194. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 63.4s OverallTime, 12 OverallIterations, 13 TraceHistogramMax, 32.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 174 SDtfs, 1014 SDslu, 1854 SDs, 0 SdLazy, 1721 SolverSat, 1222 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 622 GetRequests, 257 SyntacticMatches, 1 SemanticMatches, 363 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1478 ImplicationChecksByTransitivity, 51.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=35occurred in iteration=11, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 11 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.2s SatisfiabilityAnalysisTime, 28.4s InterpolantComputationTime, 743 NumberOfCodeBlocks, 743 NumberOfCodeBlocksAsserted, 62 NumberOfCheckSat, 720 ConstructedInterpolants, 0 QuantifiedInterpolants, 645812 SizeOfPredicates, 987 NumberOfNonLiveVariables, 3221 ConjunctsInSsa, 601 ConjunctsInUnsatCore, 23 InterpolantComputations, 1 PerfectInterpolantSequences, 596/2250 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/split.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-38-37-561.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/split.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-38-37-561.csv Completed graceful shutdown