java -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/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig15.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 13:15:37,103 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 13:15:37,105 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 13:15:37,120 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 13:15:37,120 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 13:15:37,121 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 13:15:37,125 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 13:15:37,127 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 13:15:37,129 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 13:15:37,131 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 13:15:37,132 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 13:15:37,132 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 13:15:37,133 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 13:15:37,134 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 13:15:37,134 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 13:15:37,138 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 13:15:37,140 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 13:15:37,142 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 13:15:37,155 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 13:15:37,156 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 13:15:37,157 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 13:15:37,159 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 13:15:37,159 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 13:15:37,160 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 13:15:37,161 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 13:15:37,162 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 13:15:37,166 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 13:15:37,167 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 13:15:37,168 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 13:15:37,168 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 13:15:37,169 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 13:15:37,169 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 13:15:37,170 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 13:15:37,170 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 13:15:37,171 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 13:15:37,171 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 13:15:37,192 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 13:15:37,192 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 13:15:37,193 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 13:15:37,193 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 13:15:37,194 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 13:15:37,195 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 13:15:37,197 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 13:15:37,197 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 13:15:37,197 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:15:37,197 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 13:15:37,198 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 13:15:37,198 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 13:15:37,198 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 13:15:37,198 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 13:15:37,198 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 13:15:37,198 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 13:15:37,199 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 13:15:37,202 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 13:15:37,202 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 13:15:37,256 INFO ]: Repository-Root is: /tmp [2018-06-18 13:15:37,281 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 13:15:37,285 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 13:15:37,287 INFO ]: Initializing SmtParser... [2018-06-18 13:15:37,287 INFO ]: SmtParser initialized [2018-06-18 13:15:37,288 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig15.c.smt2 [2018-06-18 13:15:37,289 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-18 13:15:37,376 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig15.c.smt2 unknown [2018-06-18 13:15:37,615 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig15.c.smt2 [2018-06-18 13:15:37,620 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 13:15:37,628 INFO ]: Walking toolchain with 4 elements. [2018-06-18 13:15:37,629 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 13:15:37,629 INFO ]: Initializing ChcToBoogie... [2018-06-18 13:15:37,629 INFO ]: ChcToBoogie initialized [2018-06-18 13:15:37,636 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,698 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37 Unit [2018-06-18 13:15:37,698 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 13:15:37,699 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 13:15:37,699 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 13:15:37,699 INFO ]: Boogie Preprocessor initialized [2018-06-18 13:15:37,722 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,722 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,735 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,735 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,740 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,741 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,746 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... [2018-06-18 13:15:37,748 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 13:15:37,749 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 13:15:37,749 INFO ]: Initializing RCFGBuilder... [2018-06-18 13:15:37,749 INFO ]: RCFGBuilder initialized [2018-06-18 13:15:37,750 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:15:37,779 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 13:15:37,779 INFO ]: Found specification of procedure False [2018-06-18 13:15:37,779 INFO ]: Found implementation of procedure False [2018-06-18 13:15:37,779 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 13:15:37,779 INFO ]: Found specification of procedure state [2018-06-18 13:15:37,779 INFO ]: Found implementation of procedure state [2018-06-18 13:15:37,779 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 13:15:37,779 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 13:15:37,779 INFO ]: Found implementation of procedure Ultimate.START [2018-06-18 13:15:38,096 INFO ]: Using library mode [2018-06-18 13:15:38,096 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:15:38 BoogieIcfgContainer [2018-06-18 13:15:38,096 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 13:15:38,098 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 13:15:38,098 INFO ]: Initializing TraceAbstraction... [2018-06-18 13:15:38,113 INFO ]: TraceAbstraction initialized [2018-06-18 13:15:38,113 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:15:37" (1/3) ... [2018-06-18 13:15:38,114 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4acdafc8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 01:15:38, skipping insertion in model container [2018-06-18 13:15:38,114 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:15:37" (2/3) ... [2018-06-18 13:15:38,115 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4acdafc8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 01:15:38, skipping insertion in model container [2018-06-18 13:15:38,115 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:15:38" (3/3) ... [2018-06-18 13:15:38,117 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 13:15:38,126 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 13:15:38,133 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 13:15:38,178 INFO ]: Using default assertion order modulation [2018-06-18 13:15:38,179 INFO ]: Interprodecural is true [2018-06-18 13:15:38,179 INFO ]: Hoare is false [2018-06-18 13:15:38,179 INFO ]: Compute interpolants for FPandBP [2018-06-18 13:15:38,179 INFO ]: Backedges is TWOTRACK [2018-06-18 13:15:38,179 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 13:15:38,179 INFO ]: Difference is false [2018-06-18 13:15:38,179 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 13:15:38,179 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 13:15:38,196 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 13:15:38,206 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 13:15:38,206 INFO ]: Found error trace [2018-06-18 13:15:38,207 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:15:38,207 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:15:38,211 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 13:15:38,212 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:15:38,213 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:15:38,251 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:38,251 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:15:38,251 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:38,280 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:38,289 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:15:38,365 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 13:15:38,367 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 13:15:38,367 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 13:15:38,368 INFO ]: Interpolant automaton has 4 states [2018-06-18 13:15:38,379 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 13:15:38,379 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:15:38,381 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 13:15:38,454 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:15:38,455 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 13:15:38,455 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 13:15:38,456 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 13:15:38,456 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:15:38,471 INFO ]: With dead ends: 13 [2018-06-18 13:15:38,471 INFO ]: Without dead ends: 13 [2018-06-18 13:15:38,475 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-18 13:15:38,492 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 13:15:38,511 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 13:15:38,515 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 13:15:38,515 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 13:15:38,516 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 13:15:38,516 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:15:38,516 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 13:15:38,516 INFO ]: Interpolant automaton has 4 states. [2018-06-18 13:15:38,516 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 13:15:38,517 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 13:15:38,517 INFO ]: Found error trace [2018-06-18 13:15:38,517 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:15:38,518 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:15:38,518 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 13:15:38,518 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:15:38,518 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:15:38,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:38,519 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:15:38,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:38,577 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:38,577 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:15:38,772 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:15:38,772 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:15:38,772 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-18 13:15:38,779 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:15:38,817 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:38,824 INFO ]: Computing forward predicates... [2018-06-18 13:15:39,332 WARN ]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-18 13:15:39,622 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:15:39,645 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:15:39,645 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-18 13:15:39,645 INFO ]: Interpolant automaton has 9 states [2018-06-18 13:15:39,646 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-18 13:15:39,646 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-18 13:15:39,646 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-18 13:15:39,991 WARN ]: Spent 186.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-18 13:15:40,148 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:15:40,148 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 13:15:40,148 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 13:15:40,148 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-18 13:15:40,148 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:15:40,149 INFO ]: With dead ends: 15 [2018-06-18 13:15:40,149 INFO ]: Without dead ends: 15 [2018-06-18 13:15:40,150 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-18 13:15:40,150 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 13:15:40,153 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 13:15:40,153 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 13:15:40,154 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 13:15:40,154 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 13:15:40,154 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:15:40,154 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 13:15:40,154 INFO ]: Interpolant automaton has 9 states. [2018-06-18 13:15:40,154 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 13:15:40,154 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 13:15:40,155 INFO ]: Found error trace [2018-06-18 13:15:40,155 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:15:40,155 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:15:40,155 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 13:15:40,155 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:15:40,155 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:15:40,156 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:40,156 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:15:40,156 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:40,195 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:40,196 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:15:40,553 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 12 [2018-06-18 13:15:40,785 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:15:40,785 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:15:40,785 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-18 13:15:40,796 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-18 13:15:40,851 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:15:40,851 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:40,854 INFO ]: Computing forward predicates... [2018-06-18 13:15:41,371 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 17 [2018-06-18 13:15:41,523 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:15:41,544 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:15:41,544 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-18 13:15:41,544 INFO ]: Interpolant automaton has 11 states [2018-06-18 13:15:41,544 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-18 13:15:41,545 INFO ]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2018-06-18 13:15:41,545 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-18 13:15:41,860 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-18 13:15:42,008 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:15:42,008 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 13:15:42,008 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 13:15:42,008 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-18 13:15:42,009 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:15:42,009 INFO ]: With dead ends: 17 [2018-06-18 13:15:42,009 INFO ]: Without dead ends: 17 [2018-06-18 13:15:42,010 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=50, Invalid=160, Unknown=0, NotChecked=0, Total=210 [2018-06-18 13:15:42,010 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 13:15:42,013 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 13:15:42,013 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 13:15:42,013 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 13:15:42,013 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 13:15:42,014 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:15:42,014 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 13:15:42,014 INFO ]: Interpolant automaton has 11 states. [2018-06-18 13:15:42,014 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 13:15:42,014 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 13:15:42,014 INFO ]: Found error trace [2018-06-18 13:15:42,015 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:15:42,015 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:15:42,015 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-18 13:15:42,015 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:15:42,015 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:15:42,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:42,016 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:15:42,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:42,090 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:42,091 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:15:42,468 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 22 [2018-06-18 13:15:42,678 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:15:42,678 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:15:42,678 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-18 13:15:42,695 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:15:42,747 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 13:15:42,747 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:42,751 INFO ]: Computing forward predicates... [2018-06-18 13:15:44,323 WARN ]: Spent 1.22 s on a formula simplification. DAG size of input: 182 DAG size of output: 42 [2018-06-18 13:15:44,713 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:15:44,737 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:15:44,737 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2018-06-18 13:15:44,738 INFO ]: Interpolant automaton has 16 states [2018-06-18 13:15:44,738 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-18 13:15:44,738 INFO ]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2018-06-18 13:15:44,738 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 16 states. [2018-06-18 13:15:45,212 WARN ]: Spent 422.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 57 [2018-06-18 13:15:45,447 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 43 [2018-06-18 13:15:45,989 WARN ]: Spent 506.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 32 [2018-06-18 13:15:46,287 WARN ]: Spent 278.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 41 [2018-06-18 13:15:46,310 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:15:46,310 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 13:15:46,312 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 13:15:46,312 INFO ]: Start accepts. Automaton has 16 states. Word has length 21 [2018-06-18 13:15:46,312 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:15:46,312 INFO ]: With dead ends: 19 [2018-06-18 13:15:46,312 INFO ]: Without dead ends: 19 [2018-06-18 13:15:46,313 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 15 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=87, Invalid=333, Unknown=0, NotChecked=0, Total=420 [2018-06-18 13:15:46,313 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 13:15:46,316 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 13:15:46,316 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 13:15:46,317 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 13:15:46,317 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 13:15:46,317 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:15:46,317 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 13:15:46,317 INFO ]: Interpolant automaton has 16 states. [2018-06-18 13:15:46,317 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 13:15:46,318 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 13:15:46,318 INFO ]: Found error trace [2018-06-18 13:15:46,318 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:15:46,318 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:15:46,318 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-18 13:15:46,318 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:15:46,318 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:15:46,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:46,319 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:15:46,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:15:46,357 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:46,358 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:15:46,675 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2018-06-18 13:15:46,784 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:15:46,784 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:15:46,784 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-18 13:15:46,790 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:15:46,816 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:15:46,816 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:15:46,820 INFO ]: Computing forward predicates... [2018-06-18 13:15:54,934 WARN ]: Spent 6.29 s on a formula simplification. DAG size of input: 497 DAG size of output: 90 [2018-06-18 13:15:55,402 WARN ]: Spent 281.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 26 [2018-06-18 13:15:56,756 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:15:56,776 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:15:56,777 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-18 13:15:56,777 INFO ]: Interpolant automaton has 16 states [2018-06-18 13:15:56,777 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-18 13:15:56,777 INFO ]: CoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2018-06-18 13:15:56,777 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-18 13:15:57,501 WARN ]: Spent 688.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 78 [2018-06-18 13:15:58,447 WARN ]: Spent 897.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 57 [2018-06-18 13:15:59,520 WARN ]: Spent 1.05 s on a formula simplification. DAG size of input: 100 DAG size of output: 68 [2018-06-18 13:16:00,558 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 101 DAG size of output: 66 [2018-06-18 13:16:01,434 WARN ]: Spent 759.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 72 [2018-06-18 13:16:01,469 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:16:01,469 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 13:16:01,469 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 13:16:01,469 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-18 13:16:01,469 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:16:01,470 INFO ]: With dead ends: 21 [2018-06-18 13:16:01,470 INFO ]: Without dead ends: 21 [2018-06-18 13:16:01,470 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 18 SyntacticMatches, 4 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 12.3s TimeCoverageRelationStatistics Valid=98, Invalid=322, Unknown=0, NotChecked=0, Total=420 [2018-06-18 13:16:01,471 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 13:16:01,473 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 13:16:01,474 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 13:16:01,474 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 13:16:01,474 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 13:16:01,474 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:16:01,474 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 13:16:01,474 INFO ]: Interpolant automaton has 16 states. [2018-06-18 13:16:01,475 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 13:16:01,475 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 13:16:01,475 INFO ]: Found error trace [2018-06-18 13:16:01,475 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:16:01,475 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:16:01,476 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-18 13:16:01,476 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:16:01,476 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:16:01,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:16:01,476 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:16:01,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:16:01,545 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:16:01,546 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:16:01,773 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-18 13:16:02,144 WARN ]: Spent 319.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-18 13:16:02,388 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:16:02,388 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:16:02,388 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-18 13:16:02,397 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 13:16:02,440 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-18 13:16:02,440 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:16:02,444 INFO ]: Computing forward predicates... [2018-06-18 13:16:20,792 WARN ]: Spent 15.63 s on a formula simplification. DAG size of input: 1608 DAG size of output: 111 [2018-06-18 13:16:21,008 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 22 [2018-06-18 13:16:21,337 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 27 [2018-06-18 13:16:22,155 WARN ]: Spent 306.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-18 13:16:24,082 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:16:24,102 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:16:24,102 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 23 [2018-06-18 13:16:24,102 INFO ]: Interpolant automaton has 23 states [2018-06-18 13:16:24,102 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-18 13:16:24,103 INFO ]: CoverageRelationStatistics Valid=72, Invalid=434, Unknown=0, NotChecked=0, Total=506 [2018-06-18 13:16:24,103 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 23 states. [2018-06-18 13:16:25,415 WARN ]: Spent 1.26 s on a formula simplification. DAG size of input: 122 DAG size of output: 80 [2018-06-18 13:16:25,957 WARN ]: Spent 461.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 32 [2018-06-18 13:16:26,606 WARN ]: Spent 599.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 55 [2018-06-18 13:16:27,167 WARN ]: Spent 470.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 49 [2018-06-18 13:16:28,144 WARN ]: Spent 946.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 56 [2018-06-18 13:16:28,821 WARN ]: Spent 647.00 ms on a formula simplification. DAG size of input: 126 DAG size of output: 57 [2018-06-18 13:16:28,982 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:16:28,982 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 13:16:28,985 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:16:28,985 INFO ]: Start accepts. Automaton has 23 states. Word has length 29 [2018-06-18 13:16:28,986 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:16:28,986 INFO ]: With dead ends: 23 [2018-06-18 13:16:28,986 INFO ]: Without dead ends: 23 [2018-06-18 13:16:28,987 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 23.2s TimeCoverageRelationStatistics Valid=161, Invalid=651, Unknown=0, NotChecked=0, Total=812 [2018-06-18 13:16:28,987 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 13:16:28,991 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 13:16:28,991 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 13:16:28,991 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 13:16:28,991 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 13:16:28,991 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:16:28,991 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 13:16:28,991 INFO ]: Interpolant automaton has 23 states. [2018-06-18 13:16:28,991 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 13:16:28,992 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 13:16:28,992 INFO ]: Found error trace [2018-06-18 13:16:28,992 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:16:28,992 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:16:28,992 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-18 13:16:28,992 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:16:28,992 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:16:28,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:16:28,993 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:16:28,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:16:29,053 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:16:29,054 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:16:29,763 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:16:29,764 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:16:29,764 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-18 13:16:29,769 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-18 13:16:29,898 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-18 13:16:29,898 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:16:29,902 INFO ]: Computing forward predicates... [2018-06-18 13:16:30,063 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 18 [2018-06-18 13:16:30,454 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 28 [2018-06-18 13:16:30,672 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 27 [2018-06-18 13:16:31,616 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:16:31,647 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:16:31,647 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-06-18 13:16:31,648 INFO ]: Interpolant automaton has 25 states [2018-06-18 13:16:31,648 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-18 13:16:31,648 INFO ]: CoverageRelationStatistics Valid=69, Invalid=531, Unknown=0, NotChecked=0, Total=600 [2018-06-18 13:16:31,648 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 25 states. [2018-06-18 13:16:32,033 WARN ]: Spent 348.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 56 [2018-06-18 13:16:32,275 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 37 [2018-06-18 13:16:32,521 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 44 [2018-06-18 13:16:32,832 WARN ]: Spent 285.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 44 [2018-06-18 13:16:33,075 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 35 [2018-06-18 13:16:33,316 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 31 [2018-06-18 13:16:33,663 WARN ]: Spent 320.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 43 [2018-06-18 13:16:33,715 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:16:33,715 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 13:16:33,716 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 13:16:33,716 INFO ]: Start accepts. Automaton has 25 states. Word has length 33 [2018-06-18 13:16:33,716 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:16:33,717 INFO ]: With dead ends: 25 [2018-06-18 13:16:33,717 INFO ]: Without dead ends: 25 [2018-06-18 13:16:33,717 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=188, Invalid=868, Unknown=0, NotChecked=0, Total=1056 [2018-06-18 13:16:33,717 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 13:16:33,721 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 13:16:33,721 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 13:16:33,721 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 13:16:33,721 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 13:16:33,722 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:16:33,722 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 13:16:33,722 INFO ]: Interpolant automaton has 25 states. [2018-06-18 13:16:33,722 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 13:16:33,722 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 13:16:33,723 INFO ]: Found error trace [2018-06-18 13:16:33,723 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:16:33,723 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:16:33,723 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-18 13:16:33,723 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:16:33,723 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:16:33,723 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:16:33,723 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:16:33,723 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:16:33,802 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:16:33,803 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:16:34,585 WARN ]: Spent 491.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-18 13:16:35,320 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-18 13:16:35,320 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:16:35,320 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-18 13:16:35,327 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:16:35,368 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:16:35,374 INFO ]: Computing forward predicates... [2018-06-18 13:16:38,868 WARN ]: Spent 3.10 s on a formula simplification. DAG size of input: 527 DAG size of output: 54 [2018-06-18 13:16:39,308 WARN ]: Spent 222.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 32 [2018-06-18 13:16:39,452 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 26 Received shutdown request... [2018-06-18 13:16:39,690 INFO ]: Timeout while computing interpolants [2018-06-18 13:16:39,890 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:16:39,890 WARN ]: Verification canceled [2018-06-18 13:16:39,896 WARN ]: Timeout [2018-06-18 13:16:39,896 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 01:16:39 BoogieIcfgContainer [2018-06-18 13:16:39,896 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 13:16:39,897 INFO ]: Toolchain (without parser) took 62275.88 ms. Allocated memory was 305.7 MB in the beginning and 827.9 MB in the end (delta: 522.2 MB). Free memory was 260.2 MB in the beginning and 640.9 MB in the end (delta: -380.7 MB). Peak memory consumption was 141.4 MB. Max. memory is 3.6 GB. [2018-06-18 13:16:39,898 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 305.7 MB. Free memory is still 271.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:16:39,899 INFO ]: ChcToBoogie took 69.66 ms. Allocated memory is still 305.7 MB. Free memory was 259.2 MB in the beginning and 256.2 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:16:39,899 INFO ]: Boogie Preprocessor took 49.47 ms. Allocated memory is still 305.7 MB. Free memory was 256.2 MB in the beginning and 255.2 MB in the end (delta: 996.7 kB). Peak memory consumption was 996.7 kB. Max. memory is 3.6 GB. [2018-06-18 13:16:39,899 INFO ]: RCFGBuilder took 347.52 ms. Allocated memory is still 305.7 MB. Free memory was 255.2 MB in the beginning and 246.2 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:16:39,900 INFO ]: TraceAbstraction took 61798.33 ms. Allocated memory was 305.7 MB in the beginning and 827.9 MB in the end (delta: 522.2 MB). Free memory was 246.2 MB in the beginning and 640.9 MB in the end (delta: -394.7 MB). Peak memory consumption was 127.5 MB. Max. memory is 3.6 GB. [2018-06-18 13:16:39,910 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 305.7 MB. Free memory is still 271.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 69.66 ms. Allocated memory is still 305.7 MB. Free memory was 259.2 MB in the beginning and 256.2 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 49.47 ms. Allocated memory is still 305.7 MB. Free memory was 256.2 MB in the beginning and 255.2 MB in the end (delta: 996.7 kB). Peak memory consumption was 996.7 kB. Max. memory is 3.6 GB. * RCFGBuilder took 347.52 ms. Allocated memory is still 305.7 MB. Free memory was 255.2 MB in the beginning and 246.2 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61798.33 ms. Allocated memory was 305.7 MB in the beginning and 827.9 MB in the end (delta: 522.2 MB). Free memory was 246.2 MB in the beginning and 640.9 MB in the end (delta: -394.7 MB). Peak memory consumption was 127.5 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 25 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.7s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 14.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 90 SDtfs, 149 SDslu, 472 SDs, 0 SdLazy, 406 SolverSat, 197 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 233 GetRequests, 102 SyntacticMatches, 10 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 394 ImplicationChecksByTransitivity, 45.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, 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, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 40.1s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 520088736 SizeOfPredicates, 271 NumberOfNonLiveVariables, 969 ConjunctsInSsa, 234 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 112/406 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/dillig15.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_13-16-39-922.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig15.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_13-16-39-922.csv Completed graceful shutdown