java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 12:25:47,021 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 12:25:47,023 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 12:25:47,037 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 12:25:47,037 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 12:25:47,074 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 12:25:47,075 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 12:25:47,077 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 12:25:47,078 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 12:25:47,080 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 12:25:47,081 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 12:25:47,081 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 12:25:47,082 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 12:25:47,083 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 12:25:47,083 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 12:25:47,086 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 12:25:47,088 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 12:25:47,090 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 12:25:47,099 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 12:25:47,100 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 12:25:47,101 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 12:25:47,105 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 12:25:47,105 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 12:25:47,106 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 12:25:47,106 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 12:25:47,107 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 12:25:47,108 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 12:25:47,108 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 12:25:47,114 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 12:25:47,114 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 12:25:47,115 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 12:25:47,116 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 12:25:47,116 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 12:25:47,118 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 12:25:47,119 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 12:25:47,120 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 12:25:47,142 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 12:25:47,142 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 12:25:47,142 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 12:25:47,143 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 12:25:47,148 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 12:25:47,149 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 12:25:47,149 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 12:25:47,149 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 12:25:47,149 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 12:25:47,149 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 12:25:47,150 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 12:25:47,150 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 12:25:47,150 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 12:25:47,150 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 12:25:47,150 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 12:25:47,151 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 12:25:47,151 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 12:25:47,151 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 12:25:47,151 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 12:25:47,155 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 12:25:47,155 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 12:25:47,204 INFO ]: Repository-Root is: /tmp [2018-06-22 12:25:47,219 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 12:25:47,223 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 12:25:47,225 INFO ]: Initializing SmtParser... [2018-06-22 12:25:47,225 INFO ]: SmtParser initialized [2018-06-22 12:25:47,225 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 [2018-06-22 12:25:47,227 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 12:25:47,318 INFO ]: Executing SMT file /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 unknown [2018-06-22 12:25:47,681 INFO ]: Succesfully executed SMT file /storage/chc-comp/sally-chc-benchmarks/lfht/lfht_2_mini_cleaned.lemma4.smt2 [2018-06-22 12:25:47,685 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 12:25:47,690 INFO ]: Walking toolchain with 4 elements. [2018-06-22 12:25:47,691 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 12:25:47,691 INFO ]: Initializing ChcToBoogie... [2018-06-22 12:25:47,691 INFO ]: ChcToBoogie initialized [2018-06-22 12:25:47,695 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,748 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47 Unit [2018-06-22 12:25:47,749 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 12:25:47,753 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 12:25:47,753 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 12:25:47,753 INFO ]: Boogie Preprocessor initialized [2018-06-22 12:25:47,774 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,774 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,784 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,795 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,801 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,803 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,814 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... [2018-06-22 12:25:47,816 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 12:25:47,817 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 12:25:47,817 INFO ]: Initializing RCFGBuilder... [2018-06-22 12:25:47,817 INFO ]: RCFGBuilder initialized [2018-06-22 12:25:47,818 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 12:25:47,827 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 12:25:47,827 INFO ]: Found specification of procedure False [2018-06-22 12:25:47,827 INFO ]: Found implementation of procedure False [2018-06-22 12:25:47,827 INFO ]: Specification and implementation of procedure invariant given in one single declaration [2018-06-22 12:25:47,827 INFO ]: Found specification of procedure invariant [2018-06-22 12:25:47,827 INFO ]: Found implementation of procedure invariant [2018-06-22 12:25:47,827 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 12:25:47,827 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 12:25:47,827 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 12:25:48,150 INFO ]: Using library mode [2018-06-22 12:25:48,150 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:25:48 BoogieIcfgContainer [2018-06-22 12:25:48,150 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 12:25:48,152 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 12:25:48,152 INFO ]: Initializing TraceAbstraction... [2018-06-22 12:25:48,158 INFO ]: TraceAbstraction initialized [2018-06-22 12:25:48,158 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:25:47" (1/3) ... [2018-06-22 12:25:48,159 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f1d490c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 12:25:48, skipping insertion in model container [2018-06-22 12:25:48,159 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:25:47" (2/3) ... [2018-06-22 12:25:48,159 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f1d490c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 12:25:48, skipping insertion in model container [2018-06-22 12:25:48,159 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:25:48" (3/3) ... [2018-06-22 12:25:48,161 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 12:25:48,175 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 12:25:48,183 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 12:25:48,257 INFO ]: Using default assertion order modulation [2018-06-22 12:25:48,263 INFO ]: Interprodecural is true [2018-06-22 12:25:48,263 INFO ]: Hoare is false [2018-06-22 12:25:48,263 INFO ]: Compute interpolants for FPandBP [2018-06-22 12:25:48,263 INFO ]: Backedges is TWOTRACK [2018-06-22 12:25:48,263 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 12:25:48,263 INFO ]: Difference is false [2018-06-22 12:25:48,263 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 12:25:48,263 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 12:25:48,280 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 12:25:48,292 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 12:25:48,292 INFO ]: Found error trace [2018-06-22 12:25:48,293 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:25:48,293 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:25:48,299 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 12:25:48,301 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:25:48,301 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:25:48,343 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:25:48,395 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:25:48,396 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:25:48,455 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:25:48,720 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 12:25:48,722 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 12:25:48,722 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 12:25:48,724 INFO ]: Interpolant automaton has 4 states [2018-06-22 12:25:48,734 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 12:25:48,734 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 12:25:48,736 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 12:25:48,818 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:25:48,840 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 12:25:48,841 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 12:25:48,842 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 12:25:48,843 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:25:48,854 INFO ]: With dead ends: 13 [2018-06-22 12:25:48,854 INFO ]: Without dead ends: 13 [2018-06-22 12:25:48,856 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 12:25:48,871 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 12:25:48,891 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 12:25:48,892 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 12:25:48,893 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 12:25:48,894 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 12:25:48,894 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:25:48,894 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 12:25:48,894 INFO ]: Interpolant automaton has 4 states. [2018-06-22 12:25:48,895 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 12:25:48,896 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 12:25:48,896 INFO ]: Found error trace [2018-06-22 12:25:48,896 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:25:48,896 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:25:48,896 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 12:25:48,896 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:25:48,896 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:25:48,897 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:25:48,897 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:25:48,897 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:25:49,019 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:25:49,534 WARN ]: Spent 282.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 9 [2018-06-22 12:25:50,364 WARN ]: Spent 760.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 33 [2018-06-22 12:25:50,441 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 12:25:50,441 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:25:50,441 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 12:25:50,463 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:25:50,524 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:25:50,536 INFO ]: Computing forward predicates... [2018-06-22 12:26:07,109 WARN ]: Spent 523.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 12:26:07,171 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 12:26:07,206 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:26:07,206 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 12:26:07,206 INFO ]: Interpolant automaton has 8 states [2018-06-22 12:26:07,207 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 12:26:07,207 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-22 12:26:07,207 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-22 12:26:07,650 WARN ]: Spent 246.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 46 [2018-06-22 12:26:07,707 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:26:07,725 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 12:26:07,726 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 12:26:07,726 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 12:26:07,726 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:26:07,726 INFO ]: With dead ends: 15 [2018-06-22 12:26:07,726 INFO ]: Without dead ends: 15 [2018-06-22 12:26:07,727 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 10 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-22 12:26:07,727 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 12:26:07,730 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 12:26:07,730 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 12:26:07,730 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 12:26:07,730 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 12:26:07,730 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:26:07,730 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 12:26:07,730 INFO ]: Interpolant automaton has 8 states. [2018-06-22 12:26:07,731 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 12:26:07,731 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 12:26:07,731 INFO ]: Found error trace [2018-06-22 12:26:07,731 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:26:07,731 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:26:07,731 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 12:26:07,731 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:26:07,731 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:26:07,732 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:26:07,732 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 12:26:07,732 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:26:07,827 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:26:08,256 WARN ]: Spent 155.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 40 [2018-06-22 12:26:08,672 WARN ]: Spent 317.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 53 [2018-06-22 12:26:08,784 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 12:26:08,784 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:26:08,784 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:26:08,798 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 12:26:08,853 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 12:26:08,853 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:26:08,858 INFO ]: Computing forward predicates... [2018-06-22 12:26:24,158 WARN ]: Spent 356.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 41 [2018-06-22 12:26:37,761 WARN ]: Spent 322.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 64 [2018-06-22 12:26:37,877 INFO ]: Checked inductivity of 10 backedges. 1 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 12:26:37,899 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 12:26:37,899 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-22 12:26:37,899 INFO ]: Interpolant automaton has 12 states [2018-06-22 12:26:37,899 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 12:26:37,900 INFO ]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2018-06-22 12:26:37,900 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 12 states. [2018-06-22 12:26:38,399 WARN ]: Spent 451.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 87 [2018-06-22 12:26:38,623 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 46 [2018-06-22 12:26:39,047 WARN ]: Spent 379.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 81 [2018-06-22 12:26:39,085 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 12:26:39,085 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 12:26:39,085 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 12:26:39,085 INFO ]: Start accepts. Automaton has 12 states. Word has length 17 [2018-06-22 12:26:39,085 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 12:26:39,086 INFO ]: With dead ends: 17 [2018-06-22 12:26:39,086 INFO ]: Without dead ends: 17 [2018-06-22 12:26:39,086 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 12 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2018-06-22 12:26:39,087 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 12:26:39,089 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 12:26:39,089 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 12:26:39,090 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 12:26:39,090 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 12:26:39,090 INFO ]: Finished accepts. word is rejected. [2018-06-22 12:26:39,090 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 12:26:39,090 INFO ]: Interpolant automaton has 12 states. [2018-06-22 12:26:39,090 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 12:26:39,090 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 12:26:39,090 INFO ]: Found error trace [2018-06-22 12:26:39,091 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 12:26:39,091 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 12:26:39,091 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 12:26:39,091 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 12:26:39,091 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 12:26:39,092 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:26:39,092 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 12:26:39,092 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 12:26:39,270 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:26:40,327 WARN ]: Spent 692.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 10 [2018-06-22 12:26:41,440 WARN ]: Spent 1.06 s on a formula simplification. DAG size of input: 116 DAG size of output: 75 [2018-06-22 12:26:42,159 WARN ]: Spent 692.00 ms on a formula simplification. DAG size of input: 182 DAG size of output: 99 [2018-06-22 12:26:42,874 WARN ]: Spent 690.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 65 [2018-06-22 12:26:43,039 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 26 [2018-06-22 12:26:43,287 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 43 [2018-06-22 12:26:43,343 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 12:26:43,343 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 12:26:43,343 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:26:43,351 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 12:26:43,409 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 12:26:43,409 INFO ]: Conjunction of SSA is unsat [2018-06-22 12:26:43,415 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 12:26:55,249 INFO ]: Timeout while computing interpolants [2018-06-22 12:26:55,450 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 12:26:55,450 WARN ]: Verification canceled [2018-06-22 12:26:55,455 WARN ]: Timeout [2018-06-22 12:26:55,455 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 12:26:55 BoogieIcfgContainer [2018-06-22 12:26:55,455 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 12:26:55,456 INFO ]: Toolchain (without parser) took 67770.43 ms. Allocated memory was 309.9 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 258.4 MB in the beginning and 1.3 GB in the end (delta: -994.9 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 12:26:55,460 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 309.9 MB. Free memory is still 275.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 12:26:55,461 INFO ]: ChcToBoogie took 62.10 ms. Allocated memory is still 309.9 MB. Free memory was 257.4 MB in the beginning and 255.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 12:26:55,461 INFO ]: Boogie Preprocessor took 62.99 ms. Allocated memory is still 309.9 MB. Free memory was 255.4 MB in the beginning and 253.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 12:26:55,462 INFO ]: RCFGBuilder took 333.62 ms. Allocated memory is still 309.9 MB. Free memory was 253.4 MB in the beginning and 238.4 MB in the end (delta: 15.0 MB). Peak memory consumption was 15.0 MB. Max. memory is 3.6 GB. [2018-06-22 12:26:55,462 INFO ]: TraceAbstraction took 67303.43 ms. Allocated memory was 309.9 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.4 MB in the beginning and 1.3 GB in the end (delta: -1.0 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 12:26:55,466 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 309.9 MB. Free memory is still 275.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 62.10 ms. Allocated memory is still 309.9 MB. Free memory was 257.4 MB in the beginning and 255.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 62.99 ms. Allocated memory is still 309.9 MB. Free memory was 255.4 MB in the beginning and 253.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 333.62 ms. Allocated memory is still 309.9 MB. Free memory was 253.4 MB in the beginning and 238.4 MB in the end (delta: 15.0 MB). Peak memory consumption was 15.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 67303.43 ms. Allocated memory was 309.9 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.4 MB in the beginning and 1.3 GB in the end (delta: -1.0 GB). Peak memory consumption was 1.3 GB. 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 22 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 6 quantified variables from 8 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 67.2s OverallTime, 4 OverallIterations, 4 TraceHistogramMax, 1.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 33 SDtfs, 14 SDslu, 95 SDs, 0 SdLazy, 67 SolverSat, 14 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 50 GetRequests, 24 SyntacticMatches, 4 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 5.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred 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.3s SatisfiabilityAnalysisTime, 48.2s InterpolantComputationTime, 69 NumberOfCodeBlocks, 69 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 64 ConstructedInterpolants, 0 QuantifiedInterpolants, 18032 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_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_12-26-55-478.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lfht_2_mini_cleaned.lemma4.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_12-26-55-478.csv Completed graceful shutdown