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/bkley.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 13:12:18,205 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 13:12:18,207 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 13:12:18,222 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 13:12:18,222 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 13:12:18,224 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 13:12:18,225 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 13:12:18,229 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 13:12:18,230 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 13:12:18,232 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 13:12:18,232 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 13:12:18,233 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 13:12:18,233 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 13:12:18,234 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 13:12:18,237 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 13:12:18,238 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 13:12:18,240 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 13:12:18,249 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 13:12:18,250 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 13:12:18,254 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 13:12:18,255 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 13:12:18,256 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 13:12:18,256 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 13:12:18,257 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 13:12:18,257 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 13:12:18,259 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 13:12:18,260 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 13:12:18,260 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 13:12:18,261 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 13:12:18,261 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 13:12:18,266 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 13:12:18,267 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 13:12:18,267 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 13:12:18,268 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 13:12:18,268 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 13:12:18,269 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 13:12:18,289 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 13:12:18,289 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 13:12:18,290 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 13:12:18,290 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 13:12:18,291 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 13:12:18,291 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 13:12:18,291 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 13:12:18,291 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 13:12:18,292 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:12:18,294 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 13:12:18,295 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 13:12:18,295 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 13:12:18,295 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 13:12:18,295 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 13:12:18,295 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 13:12:18,296 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 13:12:18,296 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 13:12:18,297 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 13:12:18,297 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 13:12:18,349 INFO ]: Repository-Root is: /tmp [2018-06-18 13:12:18,360 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 13:12:18,363 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 13:12:18,365 INFO ]: Initializing SmtParser... [2018-06-18 13:12:18,365 INFO ]: SmtParser initialized [2018-06-18 13:12:18,366 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 [2018-06-18 13:12:18,367 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:12:18,456 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 unknown [2018-06-18 13:12:18,805 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 [2018-06-18 13:12:18,810 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 13:12:18,816 INFO ]: Walking toolchain with 4 elements. [2018-06-18 13:12:18,816 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 13:12:18,816 INFO ]: Initializing ChcToBoogie... [2018-06-18 13:12:18,816 INFO ]: ChcToBoogie initialized [2018-06-18 13:12:18,826 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,929 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18 Unit [2018-06-18 13:12:18,929 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 13:12:18,930 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 13:12:18,930 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 13:12:18,930 INFO ]: Boogie Preprocessor initialized [2018-06-18 13:12:18,947 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,947 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,957 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,957 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,965 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,967 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,969 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (1/1) ... [2018-06-18 13:12:18,973 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 13:12:18,973 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 13:12:18,973 INFO ]: Initializing RCFGBuilder... [2018-06-18 13:12:18,973 INFO ]: RCFGBuilder initialized [2018-06-18 13:12:18,974 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (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 13:12:18,987 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 13:12:18,987 INFO ]: Found specification of procedure False [2018-06-18 13:12:18,987 INFO ]: Found implementation of procedure False [2018-06-18 13:12:18,987 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 13:12:18,987 INFO ]: Found specification of procedure state [2018-06-18 13:12:18,987 INFO ]: Found implementation of procedure state [2018-06-18 13:12:18,987 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 13:12:18,987 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 13:12:18,987 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 13:12:19,289 INFO ]: Using library mode [2018-06-18 13:12:19,289 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:12:19 BoogieIcfgContainer [2018-06-18 13:12:19,289 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 13:12:19,290 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 13:12:19,290 INFO ]: Initializing TraceAbstraction... [2018-06-18 13:12:19,293 INFO ]: TraceAbstraction initialized [2018-06-18 13:12:19,294 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:12:18" (1/3) ... [2018-06-18 13:12:19,295 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5e677fa8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 01:12:19, skipping insertion in model container [2018-06-18 13:12:19,295 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:12:18" (2/3) ... [2018-06-18 13:12:19,295 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5e677fa8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 01:12:19, skipping insertion in model container [2018-06-18 13:12:19,295 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:12:19" (3/3) ... [2018-06-18 13:12:19,301 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 13:12:19,311 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 13:12:19,320 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 13:12:19,363 INFO ]: Using default assertion order modulation [2018-06-18 13:12:19,363 INFO ]: Interprodecural is true [2018-06-18 13:12:19,363 INFO ]: Hoare is false [2018-06-18 13:12:19,363 INFO ]: Compute interpolants for FPandBP [2018-06-18 13:12:19,364 INFO ]: Backedges is TWOTRACK [2018-06-18 13:12:19,364 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 13:12:19,364 INFO ]: Difference is false [2018-06-18 13:12:19,364 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 13:12:19,364 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 13:12:19,382 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 13:12:19,392 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 13:12:19,392 INFO ]: Found error trace [2018-06-18 13:12:19,393 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:12:19,393 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:12:19,399 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 13:12:19,400 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:12:19,401 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:12:19,443 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:19,443 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:12:19,443 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:19,477 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:19,488 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:12:19,599 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:12:19,602 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 13:12:19,602 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 13:12:19,603 INFO ]: Interpolant automaton has 4 states [2018-06-18 13:12:19,628 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 13:12:19,629 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:12:19,631 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 13:12:19,745 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:12:19,745 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 13:12:19,745 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 13:12:19,746 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 13:12:19,747 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:12:19,756 INFO ]: With dead ends: 13 [2018-06-18 13:12:19,756 INFO ]: Without dead ends: 13 [2018-06-18 13:12:19,757 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:12:19,771 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 13:12:19,799 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 13:12:19,800 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 13:12:19,801 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 13:12:19,802 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 13:12:19,802 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:12:19,802 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 13:12:19,802 INFO ]: Interpolant automaton has 4 states. [2018-06-18 13:12:19,802 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 13:12:19,804 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 13:12:19,804 INFO ]: Found error trace [2018-06-18 13:12:19,804 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:12:19,804 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:12:19,804 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 13:12:19,804 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:12:19,804 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:12:19,805 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:19,805 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:12:19,805 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:19,894 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:19,895 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:12:20,136 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 7 [2018-06-18 13:12:20,479 WARN ]: Spent 313.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 14 [2018-06-18 13:12:20,824 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 6 [2018-06-18 13:12:20,827 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:12:20,827 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:12:20,827 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:12:20,835 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:12:20,904 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:20,915 INFO ]: Computing forward predicates... [2018-06-18 13:12:21,277 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-18 13:12:21,637 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:12:21,670 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:12:21,670 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-18 13:12:21,670 INFO ]: Interpolant automaton has 9 states [2018-06-18 13:12:21,671 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-18 13:12:21,671 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-18 13:12:21,671 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-18 13:12:21,804 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:12:21,804 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 13:12:21,806 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 13:12:21,806 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-18 13:12:21,806 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:12:21,806 INFO ]: With dead ends: 15 [2018-06-18 13:12:21,807 INFO ]: Without dead ends: 15 [2018-06-18 13:12:21,807 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-18 13:12:21,808 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 13:12:21,810 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 13:12:21,810 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 13:12:21,810 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 13:12:21,811 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 13:12:21,814 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:12:21,814 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 13:12:21,814 INFO ]: Interpolant automaton has 9 states. [2018-06-18 13:12:21,814 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 13:12:21,815 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 13:12:21,815 INFO ]: Found error trace [2018-06-18 13:12:21,815 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:12:21,815 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:12:21,815 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 13:12:21,815 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:12:21,815 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:12:21,816 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:21,816 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:12:21,816 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:21,911 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:21,911 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:12:22,255 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 11 [2018-06-18 13:12:22,429 WARN ]: Spent 142.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2018-06-18 13:12:22,638 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:12:22,638 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:12:22,638 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 13:12:22,648 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 13:12:22,707 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:12:22,707 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:22,711 INFO ]: Computing forward predicates... [2018-06-18 13:12:22,903 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 14 [2018-06-18 13:12:23,012 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:12:23,041 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:12:23,041 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-18 13:12:23,041 INFO ]: Interpolant automaton has 11 states [2018-06-18 13:12:23,041 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-18 13:12:23,041 INFO ]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2018-06-18 13:12:23,042 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-18 13:12:23,288 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 27 [2018-06-18 13:12:23,447 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:12:23,447 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 13:12:23,448 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 13:12:23,448 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-18 13:12:23,448 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:12:23,449 INFO ]: With dead ends: 17 [2018-06-18 13:12:23,449 INFO ]: Without dead ends: 17 [2018-06-18 13:12:23,449 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2018-06-18 13:12:23,449 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 13:12:23,452 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 13:12:23,452 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 13:12:23,453 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 13:12:23,453 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 13:12:23,453 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:12:23,453 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 13:12:23,453 INFO ]: Interpolant automaton has 11 states. [2018-06-18 13:12:23,453 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 13:12:23,454 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 13:12:23,454 INFO ]: Found error trace [2018-06-18 13:12:23,454 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:12:23,454 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:12:23,454 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-18 13:12:23,454 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:12:23,454 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:12:23,455 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:23,455 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:12:23,455 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:23,511 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:23,512 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:12:23,872 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:12:23,872 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:12:23,872 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:12:23,887 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:12:23,935 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 13:12:23,935 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:23,939 INFO ]: Computing forward predicates... [2018-06-18 13:12:25,083 WARN ]: Spent 877.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 20 [2018-06-18 13:12:25,260 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 23 [2018-06-18 13:12:25,590 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:12:25,610 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:12:25,610 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-18 13:12:25,611 INFO ]: Interpolant automaton has 14 states [2018-06-18 13:12:25,611 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-18 13:12:25,611 INFO ]: CoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-06-18 13:12:25,611 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 14 states. [2018-06-18 13:12:25,785 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-18 13:12:26,094 WARN ]: Spent 133.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 30 [2018-06-18 13:12:26,116 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:12:26,116 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 13:12:26,117 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 13:12:26,118 INFO ]: Start accepts. Automaton has 14 states. Word has length 21 [2018-06-18 13:12:26,118 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:12:26,118 INFO ]: With dead ends: 19 [2018-06-18 13:12:26,118 INFO ]: Without dead ends: 19 [2018-06-18 13:12:26,119 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=84, Invalid=222, Unknown=0, NotChecked=0, Total=306 [2018-06-18 13:12:26,119 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 13:12:26,122 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 13:12:26,122 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 13:12:26,123 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 13:12:26,123 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 13:12:26,123 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:12:26,123 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 13:12:26,123 INFO ]: Interpolant automaton has 14 states. [2018-06-18 13:12:26,123 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 13:12:26,124 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 13:12:26,124 INFO ]: Found error trace [2018-06-18 13:12:26,124 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:12:26,124 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:12:26,124 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-18 13:12:26,124 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:12:26,124 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:12:26,125 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:26,125 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:12:26,125 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:26,186 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:26,187 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:12:26,569 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2018-06-18 13:12:26,803 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:12:26,803 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:12:26,803 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:12:26,809 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:12:26,886 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:12:26,886 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:26,892 INFO ]: Computing forward predicates... [2018-06-18 13:12:27,720 WARN ]: Spent 534.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 24 [2018-06-18 13:12:49,635 WARN ]: Spent 20.07 s on a formula simplification. DAG size of input: 1410 DAG size of output: 100 [2018-06-18 13:12:52,307 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:12:52,341 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:12:52,341 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-18 13:12:52,341 INFO ]: Interpolant automaton has 16 states [2018-06-18 13:12:52,341 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-18 13:12:52,341 INFO ]: CoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2018-06-18 13:12:52,341 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-18 13:12:53,330 WARN ]: Spent 929.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 72 [2018-06-18 13:12:53,785 WARN ]: Spent 267.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 23 [2018-06-18 13:12:54,311 WARN ]: Spent 504.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 39 [2018-06-18 13:12:54,825 WARN ]: Spent 490.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 46 [2018-06-18 13:12:55,707 WARN ]: Spent 857.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 70 [2018-06-18 13:12:55,734 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:12:55,734 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 13:12:55,739 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 13:12:55,739 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-18 13:12:55,739 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:12:55,740 INFO ]: With dead ends: 21 [2018-06-18 13:12:55,740 INFO ]: Without dead ends: 21 [2018-06-18 13:12:55,740 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 25.5s TimeCoverageRelationStatistics Valid=102, Invalid=318, Unknown=0, NotChecked=0, Total=420 [2018-06-18 13:12:55,740 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 13:12:55,743 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 13:12:55,743 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 13:12:55,745 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 13:12:55,745 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 13:12:55,745 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:12:55,745 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 13:12:55,745 INFO ]: Interpolant automaton has 16 states. [2018-06-18 13:12:55,745 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 13:12:55,746 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 13:12:55,746 INFO ]: Found error trace [2018-06-18 13:12:55,746 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:12:55,746 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:12:55,746 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-18 13:12:55,746 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:12:55,746 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:12:55,747 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:55,747 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:12:55,747 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:12:55,862 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:55,863 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:12:57,081 WARN ]: Spent 927.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 16 [2018-06-18 13:12:57,544 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:12:57,544 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:12:57,544 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:12:57,553 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 13:12:57,640 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-18 13:12:57,640 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:12:57,645 INFO ]: Computing forward predicates... [2018-06-18 13:12:57,950 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 24 [2018-06-18 13:12:58,420 WARN ]: Spent 263.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 31 [2018-06-18 13:12:58,746 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 28 [2018-06-18 13:12:58,954 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:12:58,974 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:12:58,974 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-18 13:12:58,974 INFO ]: Interpolant automaton has 19 states [2018-06-18 13:12:58,974 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-18 13:12:58,975 INFO ]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2018-06-18 13:12:58,975 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-18 13:12:59,279 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 44 [2018-06-18 13:12:59,610 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-06-18 13:12:59,802 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 32 [2018-06-18 13:13:00,030 WARN ]: Spent 199.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 34 [2018-06-18 13:13:00,255 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 38 [2018-06-18 13:13:00,292 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:13:00,292 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 13:13:00,292 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:13:00,292 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-18 13:13:00,292 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:13:00,293 INFO ]: With dead ends: 23 [2018-06-18 13:13:00,293 INFO ]: Without dead ends: 23 [2018-06-18 13:13:00,293 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 4 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=126, Invalid=474, Unknown=0, NotChecked=0, Total=600 [2018-06-18 13:13:00,294 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 13:13:00,297 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 13:13:00,297 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 13:13:00,297 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 13:13:00,297 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 13:13:00,298 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:13:00,298 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 13:13:00,298 INFO ]: Interpolant automaton has 19 states. [2018-06-18 13:13:00,298 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 13:13:00,298 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 13:13:00,298 INFO ]: Found error trace [2018-06-18 13:13:00,298 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:13:00,299 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:13:00,299 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-18 13:13:00,299 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:13:00,299 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:13:00,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:13:00,299 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:13:00,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:13:00,417 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:13:00,418 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:13:00,867 WARN ]: Spent 134.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2018-06-18 13:13:01,078 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 35 [2018-06-18 13:13:01,315 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 35 [2018-06-18 13:13:01,662 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:13:01,662 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:13:01,662 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:13:01,671 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-18 13:13:01,807 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-18 13:13:01,807 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:13:01,815 INFO ]: Computing forward predicates... [2018-06-18 13:13:03,528 WARN ]: Spent 1.24 s on a formula simplification. DAG size of input: 198 DAG size of output: 41 [2018-06-18 13:13:03,884 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 31 [2018-06-18 13:13:04,410 WARN ]: Spent 260.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 35 [2018-06-18 13:13:05,942 WARN ]: Spent 1.10 s on a formula simplification. DAG size of input: 85 DAG size of output: 29 [2018-06-18 13:13:06,208 WARN ]: Spent 206.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 28 [2018-06-18 13:13:07,107 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:13:07,138 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:13:07,138 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 29 [2018-06-18 13:13:07,139 INFO ]: Interpolant automaton has 29 states [2018-06-18 13:13:07,139 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-18 13:13:07,139 INFO ]: CoverageRelationStatistics Valid=82, Invalid=730, Unknown=0, NotChecked=0, Total=812 [2018-06-18 13:13:07,139 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 29 states. [2018-06-18 13:13:08,552 WARN ]: Spent 1.20 s on a formula simplification. DAG size of input: 120 DAG size of output: 89 [2018-06-18 13:13:08,828 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 52 [2018-06-18 13:13:09,222 WARN ]: Spent 352.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 56 [2018-06-18 13:13:09,675 WARN ]: Spent 415.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 55 [2018-06-18 13:13:10,055 WARN ]: Spent 340.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 53 [2018-06-18 13:13:10,512 WARN ]: Spent 418.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 51 [2018-06-18 13:13:11,159 WARN ]: Spent 606.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 64 [2018-06-18 13:13:11,211 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:13:11,211 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 13:13:11,213 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 13:13:11,213 INFO ]: Start accepts. Automaton has 29 states. Word has length 33 [2018-06-18 13:13:11,213 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:13:11,214 INFO ]: With dead ends: 25 [2018-06-18 13:13:11,214 INFO ]: Without dead ends: 25 [2018-06-18 13:13:11,214 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 9.5s TimeCoverageRelationStatistics Valid=207, Invalid=1125, Unknown=0, NotChecked=0, Total=1332 [2018-06-18 13:13:11,214 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 13:13:11,218 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 13:13:11,218 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 13:13:11,219 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 13:13:11,219 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 13:13:11,219 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:13:11,219 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 13:13:11,219 INFO ]: Interpolant automaton has 29 states. [2018-06-18 13:13:11,219 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 13:13:11,220 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 13:13:11,220 INFO ]: Found error trace [2018-06-18 13:13:11,220 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:13:11,220 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:13:11,220 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-18 13:13:11,220 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:13:11,220 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:13:11,221 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:13:11,221 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:13:11,221 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:13:11,359 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:13:11,360 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:13:13,262 WARN ]: Spent 1.62 s on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-18 13:13:13,371 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 42 [2018-06-18 13:13:13,789 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 35 [2018-06-18 13:13:14,131 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 18 [2018-06-18 13:13:14,251 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:13:14,252 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:13:14,252 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:13:14,258 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:13:14,345 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:13:14,358 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-18 13:13:20,453 WARN ]: Removed 7 from assertion stack [2018-06-18 13:13:20,454 INFO ]: Timeout while computing interpolants [2018-06-18 13:13:20,654 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:13:20,654 WARN ]: Verification canceled [2018-06-18 13:13:20,658 WARN ]: Timeout [2018-06-18 13:13:20,658 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 01:13:20 BoogieIcfgContainer [2018-06-18 13:13:20,658 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 13:13:20,659 INFO ]: Toolchain (without parser) took 61848.13 ms. Allocated memory was 304.6 MB in the beginning and 886.0 MB in the end (delta: 581.4 MB). Free memory was 252.2 MB in the beginning and 744.2 MB in the end (delta: -492.0 MB). Peak memory consumption was 665.2 MB. Max. memory is 3.6 GB. [2018-06-18 13:13:20,660 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 304.6 MB. Free memory is still 270.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:13:20,660 INFO ]: ChcToBoogie took 113.01 ms. Allocated memory is still 304.6 MB. Free memory was 252.2 MB in the beginning and 247.2 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:13:20,661 INFO ]: Boogie Preprocessor took 43.34 ms. Allocated memory is still 304.6 MB. Free memory was 247.2 MB in the beginning and 246.2 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-18 13:13:20,661 INFO ]: RCFGBuilder took 316.08 ms. Allocated memory is still 304.6 MB. Free memory was 246.2 MB in the beginning and 232.2 MB in the end (delta: 14.0 MB). Peak memory consumption was 14.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:13:20,661 INFO ]: TraceAbstraction took 61367.58 ms. Allocated memory was 304.6 MB in the beginning and 886.0 MB in the end (delta: 581.4 MB). Free memory was 232.2 MB in the beginning and 744.2 MB in the end (delta: -512.0 MB). Peak memory consumption was 645.3 MB. Max. memory is 3.6 GB. [2018-06-18 13:13:20,664 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 304.6 MB. Free memory is still 270.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 113.01 ms. Allocated memory is still 304.6 MB. Free memory was 252.2 MB in the beginning and 247.2 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 43.34 ms. Allocated memory is still 304.6 MB. Free memory was 247.2 MB in the beginning and 246.2 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 316.08 ms. Allocated memory is still 304.6 MB. Free memory was 246.2 MB in the beginning and 232.2 MB in the end (delta: 14.0 MB). Peak memory consumption was 14.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61367.58 ms. Allocated memory was 304.6 MB in the beginning and 886.0 MB in the end (delta: 581.4 MB). Free memory was 232.2 MB in the beginning and 744.2 MB in the end (delta: -512.0 MB). Peak memory consumption was 645.3 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 PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 792. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.3s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 9.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 90 SDtfs, 185 SDslu, 438 SDs, 0 SdLazy, 383 SolverSat, 229 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 229 GetRequests, 106 SyntacticMatches, 8 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 351 ImplicationChecksByTransitivity, 43.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.9s SatisfiabilityAnalysisTime, 40.3s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 370936 SizeOfPredicates, 345 NumberOfNonLiveVariables, 1752 ConjunctsInSsa, 283 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/bkley.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_13-13-20-675.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bkley.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_13-13-20-675.csv Completed graceful shutdown