java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:51:15,126 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:51:15,128 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:51:15,145 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:51:15,145 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:51:15,146 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:51:15,147 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:51:15,150 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:51:15,152 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:51:15,152 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:51:15,154 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:51:15,155 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:51:15,155 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:51:15,156 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:51:15,159 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:51:15,160 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:51:15,161 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:51:15,170 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:51:15,171 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:51:15,172 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:51:15,173 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:51:15,178 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:51:15,179 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:51:15,179 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:51:15,180 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:51:15,182 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:51:15,183 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:51:15,183 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:51:15,188 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:51:15,188 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:51:15,189 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:51:15,189 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:51:15,190 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:51:15,190 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:51:15,191 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:51:15,191 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 14:51:15,210 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:51:15,210 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:51:15,210 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:51:15,210 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:51:15,211 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:51:15,211 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:51:15,212 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:51:15,212 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:51:15,212 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:51:15,212 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:51:15,212 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:51:15,213 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:51:15,213 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:51:15,213 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:51:15,213 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:51:15,213 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:51:15,213 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:51:15,214 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:51:15,214 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:51:15,215 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:51:15,215 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:51:15,261 INFO ]: Repository-Root is: /tmp [2018-06-22 14:51:15,275 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:51:15,280 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:51:15,282 INFO ]: Initializing SmtParser... [2018-06-22 14:51:15,282 INFO ]: SmtParser initialized [2018-06-22 14:51:15,283 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 [2018-06-22 14:51:15,284 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 14:51:15,381 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 unknown [2018-06-22 14:51:15,732 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bkley.c.smt2 [2018-06-22 14:51:15,739 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:51:15,747 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:51:15,748 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:51:15,748 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:51:15,748 INFO ]: ChcToBoogie initialized [2018-06-22 14:51:15,751 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,804 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15 Unit [2018-06-22 14:51:15,804 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:51:15,804 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:51:15,804 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:51:15,804 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:51:15,826 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,826 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,847 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,847 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,853 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,863 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,865 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (1/1) ... [2018-06-22 14:51:15,868 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:51:15,868 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:51:15,868 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:51:15,868 INFO ]: RCFGBuilder initialized [2018-06-22 14:51:15,869 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (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 14:51:15,894 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:51:15,894 INFO ]: Found specification of procedure False [2018-06-22 14:51:15,894 INFO ]: Found implementation of procedure False [2018-06-22 14:51:15,894 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:51:15,894 INFO ]: Found specification of procedure state [2018-06-22 14:51:15,894 INFO ]: Found implementation of procedure state [2018-06-22 14:51:15,894 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:51:15,894 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:51:15,894 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 14:51:16,195 INFO ]: Using library mode [2018-06-22 14:51:16,195 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:51:16 BoogieIcfgContainer [2018-06-22 14:51:16,195 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:51:16,197 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:51:16,197 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:51:16,199 INFO ]: TraceAbstraction initialized [2018-06-22 14:51:16,200 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:51:15" (1/3) ... [2018-06-22 14:51:16,200 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ea8a6bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:51:16, skipping insertion in model container [2018-06-22 14:51:16,200 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:15" (2/3) ... [2018-06-22 14:51:16,201 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ea8a6bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:51:16, skipping insertion in model container [2018-06-22 14:51:16,201 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:51:16" (3/3) ... [2018-06-22 14:51:16,202 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:51:16,211 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:51:16,219 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:51:16,260 INFO ]: Using default assertion order modulation [2018-06-22 14:51:16,260 INFO ]: Interprodecural is true [2018-06-22 14:51:16,260 INFO ]: Hoare is false [2018-06-22 14:51:16,261 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:51:16,261 INFO ]: Backedges is TWOTRACK [2018-06-22 14:51:16,261 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:51:16,261 INFO ]: Difference is false [2018-06-22 14:51:16,261 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:51:16,261 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:51:16,275 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:51:16,284 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:51:16,285 INFO ]: Found error trace [2018-06-22 14:51:16,285 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:16,286 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:16,291 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 14:51:16,294 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:16,295 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:16,341 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:16,341 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:16,341 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:16,375 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:16,480 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 14:51:16,482 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:51:16,482 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:51:16,483 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:51:16,494 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:51:16,494 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:51:16,496 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:51:16,593 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:16,593 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:51:16,594 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:51:16,595 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:51:16,596 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:16,609 INFO ]: With dead ends: 13 [2018-06-22 14:51:16,609 INFO ]: Without dead ends: 13 [2018-06-22 14:51:16,613 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:51:16,630 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:51:16,655 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:51:16,656 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:51:16,657 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:51:16,657 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:51:16,657 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:16,657 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:51:16,657 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:51:16,658 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:51:16,659 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:51:16,659 INFO ]: Found error trace [2018-06-22 14:51:16,659 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:16,659 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:16,659 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 14:51:16,659 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:16,659 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:16,660 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:16,660 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:16,660 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:16,766 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:16,985 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 7 [2018-06-22 14:51:17,479 WARN ]: Spent 449.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 14 [2018-06-22 14:51:17,565 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:51:17,565 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:17,565 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-22 14:51:17,572 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:17,618 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:17,629 INFO ]: Computing forward predicates... [2018-06-22 14:51:18,467 WARN ]: Spent 441.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-22 14:51:18,724 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:51:18,746 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:18,746 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 14:51:18,746 INFO ]: Interpolant automaton has 9 states [2018-06-22 14:51:18,747 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 14:51:18,747 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:51:18,747 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 14:51:19,026 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:19,026 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:51:19,028 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:51:19,028 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 14:51:19,029 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:19,029 INFO ]: With dead ends: 15 [2018-06-22 14:51:19,029 INFO ]: Without dead ends: 15 [2018-06-22 14:51:19,030 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:51:19,030 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:51:19,032 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:51:19,032 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:51:19,033 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:51:19,033 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:51:19,033 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:19,033 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:51:19,033 INFO ]: Interpolant automaton has 9 states. [2018-06-22 14:51:19,033 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:51:19,037 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:51:19,037 INFO ]: Found error trace [2018-06-22 14:51:19,037 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:19,037 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:19,037 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 14:51:19,037 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:19,037 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:19,038 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:19,038 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:19,038 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:19,090 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:19,668 WARN ]: Spent 446.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2018-06-22 14:51:19,849 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:51:19,849 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:19,849 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 14:51:19,858 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:51:19,926 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:51:19,926 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:19,930 INFO ]: Computing forward predicates... [2018-06-22 14:51:20,298 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:51:20,320 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:20,320 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 14:51:20,320 INFO ]: Interpolant automaton has 11 states [2018-06-22 14:51:20,320 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 14:51:20,320 INFO ]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2018-06-22 14:51:20,321 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 14:51:20,578 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 27 [2018-06-22 14:51:20,758 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:20,758 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 14:51:20,758 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 14:51:20,758 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 14:51:20,758 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:20,759 INFO ]: With dead ends: 17 [2018-06-22 14:51:20,759 INFO ]: Without dead ends: 17 [2018-06-22 14:51:20,759 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2018-06-22 14:51:20,760 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 14:51:20,762 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 14:51:20,762 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 14:51:20,763 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 14:51:20,763 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 14:51:20,763 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:20,763 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 14:51:20,763 INFO ]: Interpolant automaton has 11 states. [2018-06-22 14:51:20,763 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 14:51:20,764 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 14:51:20,764 INFO ]: Found error trace [2018-06-22 14:51:20,764 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:20,764 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:20,764 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 14:51:20,764 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:20,764 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:20,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:20,765 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:20,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:20,816 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:21,189 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 14:51:21,190 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:21,190 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) [2018-06-22 14:51:21,214 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:51:21,278 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 14:51:21,278 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:21,283 INFO ]: Computing forward predicates... [2018-06-22 14:51:22,396 WARN ]: Spent 806.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 20 [2018-06-22 14:51:22,603 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 23 [2018-06-22 14:51:22,771 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 14:51:22,792 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:22,792 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-22 14:51:22,792 INFO ]: Interpolant automaton has 14 states [2018-06-22 14:51:22,792 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 14:51:22,792 INFO ]: CoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-06-22 14:51:22,792 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 14 states. [2018-06-22 14:51:22,958 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 34 [2018-06-22 14:51:23,294 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 30 [2018-06-22 14:51:23,441 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:23,442 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 14:51:23,443 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 14:51:23,443 INFO ]: Start accepts. Automaton has 14 states. Word has length 21 [2018-06-22 14:51:23,443 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:23,444 INFO ]: With dead ends: 19 [2018-06-22 14:51:23,444 INFO ]: Without dead ends: 19 [2018-06-22 14:51:23,444 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-22 14:51:23,444 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 14:51:23,447 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 14:51:23,447 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 14:51:23,447 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 14:51:23,447 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 14:51:23,447 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:23,448 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 14:51:23,448 INFO ]: Interpolant automaton has 14 states. [2018-06-22 14:51:23,448 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 14:51:23,448 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 14:51:23,448 INFO ]: Found error trace [2018-06-22 14:51:23,448 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:23,448 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:23,449 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 14:51:23,449 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:23,449 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:23,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:23,449 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:23,449 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:23,518 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:24,852 WARN ]: Spent 1.09 s on a formula simplification. DAG size of input: 18 DAG size of output: 14 [2018-06-22 14:51:25,053 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2018-06-22 14:51:25,262 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:51:25,263 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:25,263 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:51:25,269 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 14:51:25,325 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 14:51:25,325 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:25,329 INFO ]: Computing forward predicates... [2018-06-22 14:51:25,829 WARN ]: Spent 382.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 24 [2018-06-22 14:51:47,414 WARN ]: Spent 19.72 s on a formula simplification. DAG size of input: 1410 DAG size of output: 100 [2018-06-22 14:51:51,390 WARN ]: Spent 129.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 5 [2018-06-22 14:51:51,396 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:51:51,436 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:51,436 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 14:51:51,436 INFO ]: Interpolant automaton has 16 states [2018-06-22 14:51:51,436 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 14:51:51,436 INFO ]: CoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2018-06-22 14:51:51,436 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 14:51:52,424 WARN ]: Spent 926.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 72 [2018-06-22 14:51:52,920 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 23 [2018-06-22 14:51:53,496 WARN ]: Spent 510.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 39 [2018-06-22 14:51:54,011 WARN ]: Spent 489.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 46 [2018-06-22 14:51:54,916 WARN ]: Spent 841.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 70 [2018-06-22 14:51:54,989 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:54,989 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 14:51:54,992 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 14:51:54,992 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 14:51:54,993 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:54,993 INFO ]: With dead ends: 21 [2018-06-22 14:51:54,993 INFO ]: Without dead ends: 21 [2018-06-22 14:51:54,994 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 26.3s TimeCoverageRelationStatistics Valid=102, Invalid=318, Unknown=0, NotChecked=0, Total=420 [2018-06-22 14:51:54,994 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 14:51:54,997 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 14:51:54,997 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 14:51:54,997 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 14:51:54,997 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 14:51:54,997 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:54,997 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 14:51:54,997 INFO ]: Interpolant automaton has 16 states. [2018-06-22 14:51:54,998 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 14:51:54,998 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 14:51:54,998 INFO ]: Found error trace [2018-06-22 14:51:54,998 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:54,999 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:54,999 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 14:51:54,999 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:54,999 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:54,999 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:54,999 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:54,999 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:55,101 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:55,615 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 5 [2018-06-22 14:51:56,224 WARN ]: Spent 555.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 22 [2018-06-22 14:51:56,708 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:51:56,708 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:56,708 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:51:56,714 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 14:51:56,794 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 14:51:56,794 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:56,800 INFO ]: Computing forward predicates... [2018-06-22 14:51:57,183 WARN ]: Spent 211.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 24 [2018-06-22 14:51:57,635 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 31 [2018-06-22 14:51:57,943 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 28 [2018-06-22 14:51:58,184 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:51:58,204 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:58,204 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 14:51:58,204 INFO ]: Interpolant automaton has 19 states [2018-06-22 14:51:58,204 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 14:51:58,204 INFO ]: CoverageRelationStatistics Valid=50, Invalid=292, Unknown=0, NotChecked=0, Total=342 [2018-06-22 14:51:58,205 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 14:51:58,696 WARN ]: Spent 469.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 44 [2018-06-22 14:51:58,870 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 26 [2018-06-22 14:51:59,068 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 32 [2018-06-22 14:51:59,268 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 32 [2018-06-22 14:51:59,498 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 34 [2018-06-22 14:51:59,758 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 39 [2018-06-22 14:51:59,825 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:59,825 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 14:51:59,825 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 14:51:59,826 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 14:51:59,826 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:59,826 INFO ]: With dead ends: 23 [2018-06-22 14:51:59,826 INFO ]: Without dead ends: 23 [2018-06-22 14:51:59,827 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 4 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=125, Invalid=475, Unknown=0, NotChecked=0, Total=600 [2018-06-22 14:51:59,827 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 14:51:59,830 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 14:51:59,830 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 14:51:59,831 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 14:51:59,831 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 14:51:59,831 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:59,831 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 14:51:59,831 INFO ]: Interpolant automaton has 19 states. [2018-06-22 14:51:59,831 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 14:51:59,832 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 14:51:59,832 INFO ]: Found error trace [2018-06-22 14:51:59,832 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:59,832 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:59,832 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 14:51:59,832 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:59,832 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:59,833 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:59,833 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:59,833 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:59,948 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:00,418 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 32 [2018-06-22 14:52:00,793 WARN ]: Spent 155.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 35 [2018-06-22 14:52:01,149 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:52:01,149 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:01,149 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:52:01,155 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 14:52:01,249 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 14:52:01,249 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:01,256 INFO ]: Computing forward predicates... [2018-06-22 14:52:02,726 WARN ]: Spent 1.16 s on a formula simplification. DAG size of input: 198 DAG size of output: 41 [2018-06-22 14:52:03,002 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 31 [2018-06-22 14:52:03,432 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 35 [2018-06-22 14:52:05,160 WARN ]: Spent 1.23 s on a formula simplification. DAG size of input: 85 DAG size of output: 29 [2018-06-22 14:52:05,425 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 28 [2018-06-22 14:52:06,381 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:52:06,411 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:06,411 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 29 [2018-06-22 14:52:06,411 INFO ]: Interpolant automaton has 29 states [2018-06-22 14:52:06,412 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 14:52:06,412 INFO ]: CoverageRelationStatistics Valid=82, Invalid=730, Unknown=0, NotChecked=0, Total=812 [2018-06-22 14:52:06,412 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 29 states. [2018-06-22 14:52:07,744 WARN ]: Spent 1.16 s on a formula simplification. DAG size of input: 120 DAG size of output: 89 [2018-06-22 14:52:08,043 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 52 [2018-06-22 14:52:08,426 WARN ]: Spent 345.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 56 [2018-06-22 14:52:08,864 WARN ]: Spent 402.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 55 [2018-06-22 14:52:09,234 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 53 [2018-06-22 14:52:09,688 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 51 [2018-06-22 14:52:10,322 WARN ]: Spent 592.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 64 [2018-06-22 14:52:10,371 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:10,371 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 14:52:10,371 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 14:52:10,371 INFO ]: Start accepts. Automaton has 29 states. Word has length 33 [2018-06-22 14:52:10,372 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:10,372 INFO ]: With dead ends: 25 [2018-06-22 14:52:10,372 INFO ]: Without dead ends: 25 [2018-06-22 14:52:10,373 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 9.0s TimeCoverageRelationStatistics Valid=207, Invalid=1125, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 14:52:10,373 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 14:52:10,376 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 14:52:10,377 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 14:52:10,378 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 14:52:10,378 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 14:52:10,379 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:10,379 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 14:52:10,379 INFO ]: Interpolant automaton has 29 states. [2018-06-22 14:52:10,379 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 14:52:10,380 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 14:52:10,380 INFO ]: Found error trace [2018-06-22 14:52:10,380 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:10,380 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:10,380 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 14:52:10,380 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:10,380 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:10,380 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:10,380 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:52:10,380 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:10,478 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:11,968 WARN ]: Spent 1.22 s on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-22 14:52:12,075 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 42 [2018-06-22 14:52:12,519 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 35 [2018-06-22 14:52:12,901 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:52:12,901 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:12,915 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:52:12,921 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:52:13,004 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:13,012 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 14:52:16,073 WARN ]: Removed 2 from assertion stack [2018-06-22 14:52:16,073 INFO ]: Timeout while computing interpolants [2018-06-22 14:52:16,273 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:52:16,273 WARN ]: Verification canceled [2018-06-22 14:52:16,277 WARN ]: Timeout [2018-06-22 14:52:16,277 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:52:16 BoogieIcfgContainer [2018-06-22 14:52:16,277 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:52:16,278 INFO ]: Toolchain (without parser) took 60538.42 ms. Allocated memory was 307.2 MB in the beginning and 895.0 MB in the end (delta: 587.7 MB). Free memory was 254.7 MB in the beginning and 755.0 MB in the end (delta: -500.3 MB). Peak memory consumption was 648.3 MB. Max. memory is 3.6 GB. [2018-06-22 14:52:16,279 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:52:16,279 INFO ]: ChcToBoogie took 56.31 ms. Allocated memory is still 307.2 MB. Free memory was 254.7 MB in the beginning and 252.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:52:16,280 INFO ]: Boogie Preprocessor took 63.49 ms. Allocated memory is still 307.2 MB. Free memory was 252.7 MB in the beginning and 250.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:52:16,280 INFO ]: RCFGBuilder took 327.15 ms. Allocated memory is still 307.2 MB. Free memory was 250.7 MB in the beginning and 237.7 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:52:16,280 INFO ]: TraceAbstraction took 60080.77 ms. Allocated memory was 307.2 MB in the beginning and 895.0 MB in the end (delta: 587.7 MB). Free memory was 237.7 MB in the beginning and 755.0 MB in the end (delta: -517.3 MB). Peak memory consumption was 631.3 MB. Max. memory is 3.6 GB. [2018-06-22 14:52:16,283 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 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 56.31 ms. Allocated memory is still 307.2 MB. Free memory was 254.7 MB in the beginning and 252.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 63.49 ms. Allocated memory is still 307.2 MB. Free memory was 252.7 MB in the beginning and 250.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 327.15 ms. Allocated memory is still 307.2 MB. Free memory was 250.7 MB in the beginning and 237.7 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 60080.77 ms. Allocated memory was 307.2 MB in the beginning and 895.0 MB in the end (delta: 587.7 MB). Free memory was 237.7 MB in the beginning and 755.0 MB in the end (delta: -517.3 MB). Peak memory consumption was 631.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, 60.0s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 10.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 90 SDtfs, 185 SDslu, 444 SDs, 0 SdLazy, 387 SolverSat, 229 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 229 GetRequests, 106 SyntacticMatches, 8 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 346 ImplicationChecksByTransitivity, 44.1s 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.8s SatisfiabilityAnalysisTime, 42.1s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 370852 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_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-52-16-294.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bkley.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-52-16-294.csv Completed graceful shutdown