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/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 11:56:54,158 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 11:56:54,160 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 11:56:54,187 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 11:56:54,187 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 11:56:54,188 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 11:56:54,189 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 11:56:54,192 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 11:56:54,194 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 11:56:54,196 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 11:56:54,196 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 11:56:54,197 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 11:56:54,198 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 11:56:54,202 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 11:56:54,202 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 11:56:54,203 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 11:56:54,214 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 11:56:54,216 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 11:56:54,218 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 11:56:54,219 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 11:56:54,226 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 11:56:54,229 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 11:56:54,229 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 11:56:54,229 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 11:56:54,230 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 11:56:54,234 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 11:56:54,235 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 11:56:54,235 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 11:56:54,236 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 11:56:54,237 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 11:56:54,242 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 11:56:54,243 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 11:56:54,243 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 11:56:54,244 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 11:56:54,244 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 11:56:54,247 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 11:56:54,269 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 11:56:54,270 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 11:56:54,270 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 11:56:54,270 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 11:56:54,271 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 11:56:54,275 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 11:56:54,275 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 11:56:54,275 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 11:56:54,275 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 11:56:54,275 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 11:56:54,276 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 11:56:54,276 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 11:56:54,276 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 11:56:54,276 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 11:56:54,276 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 11:56:54,276 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 11:56:54,277 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 11:56:54,279 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 11:56:54,280 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 11:56:54,330 INFO ]: Repository-Root is: /tmp [2018-06-18 11:56:54,346 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 11:56:54,351 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 11:56:54,353 INFO ]: Initializing SmtParser... [2018-06-18 11:56:54,354 INFO ]: SmtParser initialized [2018-06-18 11:56:54,354 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 [2018-06-18 11:56:54,355 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 11:56:54,451 INFO ]: Executing SMT file /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 unknown [2018-06-18 11:56:54,786 INFO ]: Succesfully executed SMT file /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 [2018-06-18 11:56:54,791 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 11:56:54,797 INFO ]: Walking toolchain with 4 elements. [2018-06-18 11:56:54,798 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 11:56:54,798 INFO ]: Initializing ChcToBoogie... [2018-06-18 11:56:54,798 INFO ]: ChcToBoogie initialized [2018-06-18 11:56:54,805 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 11:56:54" (1/1) ... [2018-06-18 11:56:55,144 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55 Unit [2018-06-18 11:56:55,145 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 11:56:55,145 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 11:56:55,145 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 11:56:55,145 INFO ]: Boogie Preprocessor initialized [2018-06-18 11:56:55,169 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,169 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,199 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,199 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,231 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,232 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,240 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (1/1) ... [2018-06-18 11:56:55,250 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 11:56:55,251 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 11:56:55,251 INFO ]: Initializing RCFGBuilder... [2018-06-18 11:56:55,251 INFO ]: RCFGBuilder initialized [2018-06-18 11:56:55,252 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (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-18 11:56:55,272 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 11:56:55,272 INFO ]: Found specification of procedure False [2018-06-18 11:56:55,272 INFO ]: Found implementation of procedure False [2018-06-18 11:56:55,272 INFO ]: Specification and implementation of procedure invariant given in one single declaration [2018-06-18 11:56:55,272 INFO ]: Found specification of procedure invariant [2018-06-18 11:56:55,272 INFO ]: Found implementation of procedure invariant [2018-06-18 11:56:55,272 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 11:56:55,272 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 11:56:55,272 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-18 11:56:55,873 INFO ]: Using library mode [2018-06-18 11:56:55,873 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 11:56:55 BoogieIcfgContainer [2018-06-18 11:56:55,874 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 11:56:55,875 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 11:56:55,875 INFO ]: Initializing TraceAbstraction... [2018-06-18 11:56:55,880 INFO ]: TraceAbstraction initialized [2018-06-18 11:56:55,880 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 11:56:54" (1/3) ... [2018-06-18 11:56:55,881 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6003593b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 11:56:55, skipping insertion in model container [2018-06-18 11:56:55,881 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 11:56:55" (2/3) ... [2018-06-18 11:56:55,881 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6003593b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 11:56:55, skipping insertion in model container [2018-06-18 11:56:55,881 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 11:56:55" (3/3) ... [2018-06-18 11:56:55,884 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 11:56:55,895 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 11:56:55,907 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 11:56:55,963 INFO ]: Using default assertion order modulation [2018-06-18 11:56:55,964 INFO ]: Interprodecural is true [2018-06-18 11:56:55,964 INFO ]: Hoare is false [2018-06-18 11:56:55,964 INFO ]: Compute interpolants for FPandBP [2018-06-18 11:56:55,964 INFO ]: Backedges is TWOTRACK [2018-06-18 11:56:55,964 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 11:56:55,964 INFO ]: Difference is false [2018-06-18 11:56:55,964 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 11:56:55,964 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 11:56:55,985 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 11:56:56,007 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 11:56:56,007 INFO ]: Found error trace [2018-06-18 11:56:56,009 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 11:56:56,009 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 11:56:56,015 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 11:56:56,017 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 11:56:56,018 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 11:56:56,072 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:56:56,072 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 11:56:56,072 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:56:56,144 INFO ]: Conjunction of SSA is unsat [2018-06-18 11:56:56,156 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 11:56:56,516 WARN ]: Spent 247.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 9 [2018-06-18 11:56:56,609 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 11:56:56,612 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 11:56:56,612 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 11:56:56,613 INFO ]: Interpolant automaton has 4 states [2018-06-18 11:56:56,626 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 11:56:56,627 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 11:56:56,629 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 11:56:56,729 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 11:56:56,729 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 11:56:56,729 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 11:56:56,731 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 11:56:56,731 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 11:56:56,750 INFO ]: With dead ends: 13 [2018-06-18 11:56:56,751 INFO ]: Without dead ends: 13 [2018-06-18 11:56:56,754 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 11:56:56,775 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 11:56:56,809 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 11:56:56,810 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 11:56:56,811 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 11:56:56,813 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 11:56:56,813 INFO ]: Finished accepts. word is rejected. [2018-06-18 11:56:56,813 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 11:56:56,813 INFO ]: Interpolant automaton has 4 states. [2018-06-18 11:56:56,813 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 11:56:56,815 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 11:56:56,815 INFO ]: Found error trace [2018-06-18 11:56:56,815 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 11:56:56,815 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 11:56:56,815 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 11:56:56,815 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 11:56:56,815 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 11:56:56,816 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:56:56,816 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 11:56:56,816 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:56:57,045 INFO ]: Conjunction of SSA is unsat [2018-06-18 11:56:57,082 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 11:56:57,460 WARN ]: Spent 158.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 9 [2018-06-18 11:56:57,635 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 20 [2018-06-18 11:56:57,726 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 11:56:57,727 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 11:56:57,727 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 11:56:57,748 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 11:56:57,839 INFO ]: Conjunction of SSA is unsat [2018-06-18 11:56:57,854 INFO ]: Computing forward predicates... [2018-06-18 11:57:22,246 WARN ]: Spent 1.21 s on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-18 11:57:22,302 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 11:57:22,324 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 11:57:22,325 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-18 11:57:22,325 INFO ]: Interpolant automaton has 8 states [2018-06-18 11:57:22,325 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-18 11:57:22,325 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-18 11:57:22,326 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-18 11:57:22,573 WARN ]: Spent 195.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 46 [2018-06-18 11:57:22,594 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 11:57:22,594 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 11:57:22,595 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 11:57:22,595 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-18 11:57:22,595 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 11:57:22,595 INFO ]: With dead ends: 15 [2018-06-18 11:57:22,595 INFO ]: Without dead ends: 15 [2018-06-18 11:57:22,596 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-18 11:57:22,596 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 11:57:22,598 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 11:57:22,598 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 11:57:22,599 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 11:57:22,599 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 11:57:22,599 INFO ]: Finished accepts. word is rejected. [2018-06-18 11:57:22,599 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 11:57:22,599 INFO ]: Interpolant automaton has 8 states. [2018-06-18 11:57:22,599 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 11:57:22,600 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 11:57:22,600 INFO ]: Found error trace [2018-06-18 11:57:22,600 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 11:57:22,600 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 11:57:22,600 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 11:57:22,600 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 11:57:22,600 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 11:57:22,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:57:22,601 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 11:57:22,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:57:22,766 INFO ]: Conjunction of SSA is unsat [2018-06-18 11:57:22,767 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 11:57:23,116 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 17 [2018-06-18 11:57:23,348 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 38 [2018-06-18 11:57:23,629 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 17 [2018-06-18 11:57:23,661 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 11:57:23,661 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 11:57:23,661 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 11:57:23,701 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 11:57:23,758 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 11:57:23,758 INFO ]: Conjunction of SSA is unsat [2018-06-18 11:57:23,765 INFO ]: Computing forward predicates... [2018-06-18 11:57:40,376 WARN ]: Spent 209.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-18 11:57:58,131 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 64 [2018-06-18 11:57:58,268 INFO ]: Checked inductivity of 10 backedges. 1 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 11:57:58,291 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 11:57:58,291 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-18 11:57:58,291 INFO ]: Interpolant automaton has 14 states [2018-06-18 11:57:58,292 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-18 11:57:58,292 INFO ]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2018-06-18 11:57:58,292 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 14 states. [2018-06-18 11:57:58,810 WARN ]: Spent 424.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 75 [2018-06-18 11:57:59,137 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 43 [2018-06-18 11:58:00,376 WARN ]: Spent 1.21 s on a formula simplification. DAG size of input: 91 DAG size of output: 74 [2018-06-18 11:58:00,802 WARN ]: Spent 395.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 84 [2018-06-18 11:58:00,856 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 11:58:00,856 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 11:58:00,857 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 11:58:00,857 INFO ]: Start accepts. Automaton has 14 states. Word has length 17 [2018-06-18 11:58:00,857 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 11:58:00,858 INFO ]: With dead ends: 19 [2018-06-18 11:58:00,858 INFO ]: Without dead ends: 19 [2018-06-18 11:58:00,859 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=84, Invalid=258, Unknown=0, NotChecked=0, Total=342 [2018-06-18 11:58:00,859 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 11:58:00,862 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 11:58:00,862 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 11:58:00,863 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 11:58:00,863 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-18 11:58:00,863 INFO ]: Finished accepts. word is rejected. [2018-06-18 11:58:00,863 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 11:58:00,863 INFO ]: Interpolant automaton has 14 states. [2018-06-18 11:58:00,863 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 11:58:00,864 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 11:58:00,864 INFO ]: Found error trace [2018-06-18 11:58:00,864 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 11:58:00,864 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 11:58:00,864 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 3 times [2018-06-18 11:58:00,864 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 11:58:00,864 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 11:58:00,865 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:58:00,865 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 11:58:00,865 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 11:58:01,162 INFO ]: Conjunction of SSA is unsat [2018-06-18 11:58:01,163 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. Received shutdown request... [2018-06-18 11:58:01,512 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-18 11:58:01,520 WARN ]: Verification canceled [2018-06-18 11:58:01,525 WARN ]: Timeout [2018-06-18 11:58:01,526 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 11:58:01 BoogieIcfgContainer [2018-06-18 11:58:01,526 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 11:58:01,527 INFO ]: Toolchain (without parser) took 66735.00 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 257.2 MB in the beginning and 1.2 GB in the end (delta: -950.4 MB). Peak memory consumption was 241.3 MB. Max. memory is 3.6 GB. [2018-06-18 11:58:01,528 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 11:58:01,528 INFO ]: ChcToBoogie took 347.44 ms. Allocated memory was 308.8 MB in the beginning and 336.1 MB in the end (delta: 27.3 MB). Free memory was 255.2 MB in the beginning and 303.8 MB in the end (delta: -48.6 MB). Peak memory consumption was 74.5 MB. Max. memory is 3.6 GB. [2018-06-18 11:58:01,529 INFO ]: Boogie Preprocessor took 104.85 ms. Allocated memory is still 336.1 MB. Free memory was 303.8 MB in the beginning and 300.5 MB in the end (delta: 3.3 MB). Peak memory consumption was 3.3 MB. Max. memory is 3.6 GB. [2018-06-18 11:58:01,529 INFO ]: RCFGBuilder took 622.79 ms. Allocated memory is still 336.1 MB. Free memory was 300.5 MB in the beginning and 268.8 MB in the end (delta: 31.7 MB). Peak memory consumption was 31.7 MB. Max. memory is 3.6 GB. [2018-06-18 11:58:01,529 INFO ]: TraceAbstraction took 65650.64 ms. Allocated memory was 336.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 268.8 MB in the beginning and 1.2 GB in the end (delta: -938.8 MB). Peak memory consumption was 225.7 MB. Max. memory is 3.6 GB. [2018-06-18 11:58:01,533 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 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 347.44 ms. Allocated memory was 308.8 MB in the beginning and 336.1 MB in the end (delta: 27.3 MB). Free memory was 255.2 MB in the beginning and 303.8 MB in the end (delta: -48.6 MB). Peak memory consumption was 74.5 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 104.85 ms. Allocated memory is still 336.1 MB. Free memory was 303.8 MB in the beginning and 300.5 MB in the end (delta: 3.3 MB). Peak memory consumption was 3.3 MB. Max. memory is 3.6 GB. * RCFGBuilder took 622.79 ms. Allocated memory is still 336.1 MB. Free memory was 300.5 MB in the beginning and 268.8 MB in the end (delta: 31.7 MB). Peak memory consumption was 31.7 MB. Max. memory is 3.6 GB. * TraceAbstraction took 65650.64 ms. Allocated memory was 336.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 268.8 MB in the beginning and 1.2 GB in the end (delta: -938.8 MB). Peak memory consumption was 225.7 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 26 with TraceHistMax 5, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while NestedInterpolantsBuilder was constructing predicates for 24 interpolants. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 65.5s OverallTime, 4 OverallIterations, 5 TraceHistogramMax, 2.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 33 SDtfs, 14 SDslu, 95 SDs, 0 SdLazy, 67 SolverSat, 15 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 52 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 6.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=3, 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, 3 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 60.9s InterpolantComputationTime, 69 NumberOfCodeBlocks, 69 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 64 ConstructedInterpolants, 0 QuantifiedInterpolants, 18016 SizeOfPredicates, 103 NumberOfNonLiveVariables, 308 ConjunctsInSsa, 64 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 9/26 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/lfht_2_mini_cleaned.lemma4.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_11-58-01-545.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lfht_2_mini_cleaned.lemma4.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_11-58-01-545.csv Completed graceful shutdown