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/bk-nat.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:51:37,999 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:51:38,001 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:51:38,012 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:51:38,012 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:51:38,013 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:51:38,015 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:51:38,016 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:51:38,018 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:51:38,019 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:51:38,020 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:51:38,020 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:51:38,021 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:51:38,022 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:51:38,023 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:51:38,024 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:51:38,026 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:51:38,028 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:51:38,029 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:51:38,030 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:51:38,031 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:51:38,034 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:51:38,034 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:51:38,034 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:51:38,035 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:51:38,036 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:51:38,037 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:51:38,037 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:51:38,039 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:51:38,039 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:51:38,039 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:51:38,040 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:51:38,040 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:51:38,041 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:51:38,042 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:51:38,042 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:38,070 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:51:38,070 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:51:38,071 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:51:38,071 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:51:38,072 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:51:38,072 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:51:38,072 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:51:38,073 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:51:38,073 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:51:38,073 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:51:38,073 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:51:38,074 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:51:38,074 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:51:38,074 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:51:38,075 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:51:38,075 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:51:38,075 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:51:38,075 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:51:38,075 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:51:38,086 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:51:38,086 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:51:38,125 INFO ]: Repository-Root is: /tmp [2018-06-22 14:51:38,137 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:51:38,141 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:51:38,142 INFO ]: Initializing SmtParser... [2018-06-22 14:51:38,143 INFO ]: SmtParser initialized [2018-06-22 14:51:38,144 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/bk-nat.c.smt2 [2018-06-22 14:51:38,145 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:38,238 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bk-nat.c.smt2 unknown [2018-06-22 14:51:38,559 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/bk-nat.c.smt2 [2018-06-22 14:51:38,563 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:51:38,571 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:51:38,572 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:51:38,572 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:51:38,572 INFO ]: ChcToBoogie initialized [2018-06-22 14:51:38,575 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,625 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38 Unit [2018-06-22 14:51:38,625 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:51:38,626 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:51:38,626 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:51:38,626 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:51:38,646 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,646 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,660 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,660 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,667 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,668 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,670 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (1/1) ... [2018-06-22 14:51:38,672 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:51:38,673 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:51:38,673 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:51:38,673 INFO ]: RCFGBuilder initialized [2018-06-22 14:51:38,674 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (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:38,704 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:51:38,704 INFO ]: Found specification of procedure False [2018-06-22 14:51:38,704 INFO ]: Found implementation of procedure False [2018-06-22 14:51:38,704 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:51:38,705 INFO ]: Found specification of procedure state [2018-06-22 14:51:38,705 INFO ]: Found implementation of procedure state [2018-06-22 14:51:38,705 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:51:38,705 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:51:38,705 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:38,955 INFO ]: Using library mode [2018-06-22 14:51:38,956 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:51:38 BoogieIcfgContainer [2018-06-22 14:51:38,956 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:51:38,961 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:51:38,961 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:51:38,966 INFO ]: TraceAbstraction initialized [2018-06-22 14:51:38,966 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:51:38" (1/3) ... [2018-06-22 14:51:38,967 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3084fb50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:51:38, skipping insertion in model container [2018-06-22 14:51:38,967 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:51:38" (2/3) ... [2018-06-22 14:51:38,968 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3084fb50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:51:38, skipping insertion in model container [2018-06-22 14:51:38,968 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:51:38" (3/3) ... [2018-06-22 14:51:38,971 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:51:38,981 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:51:38,991 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:51:39,036 INFO ]: Using default assertion order modulation [2018-06-22 14:51:39,036 INFO ]: Interprodecural is true [2018-06-22 14:51:39,036 INFO ]: Hoare is false [2018-06-22 14:51:39,036 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:51:39,036 INFO ]: Backedges is TWOTRACK [2018-06-22 14:51:39,036 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:51:39,036 INFO ]: Difference is false [2018-06-22 14:51:39,036 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:51:39,036 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:51:39,049 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:51:39,062 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:51:39,062 INFO ]: Found error trace [2018-06-22 14:51:39,063 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:39,063 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:39,072 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 14:51:39,074 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:39,074 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:39,107 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:39,107 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:39,107 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:39,140 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:39,424 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:39,427 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:51:39,427 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:51:39,429 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:51:39,443 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:51:39,443 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:51:39,445 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:51:39,562 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:39,563 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:51:39,564 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:51:39,565 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:51:39,566 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:39,575 INFO ]: With dead ends: 13 [2018-06-22 14:51:39,575 INFO ]: Without dead ends: 13 [2018-06-22 14:51:39,577 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:51:39,591 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:51:39,612 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:51:39,613 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:51:39,614 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:51:39,615 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:51:39,615 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:39,615 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:51:39,615 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:51:39,615 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:51:39,616 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:51:39,616 INFO ]: Found error trace [2018-06-22 14:51:39,616 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:39,616 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:39,616 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 14:51:39,616 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:39,616 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:39,617 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:39,617 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:39,617 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:39,695 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:40,061 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:40,061 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:40,061 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:40,068 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:40,123 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:40,130 INFO ]: Computing forward predicates... [2018-06-22 14:51:40,497 WARN ]: Spent 148.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 14:51:40,877 WARN ]: Spent 205.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 14:51:41,120 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:41,156 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:41,156 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 14:51:41,157 INFO ]: Interpolant automaton has 9 states [2018-06-22 14:51:41,157 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 14:51:41,157 INFO ]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:51:41,157 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 14:51:41,379 WARN ]: Spent 181.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 14:51:41,575 WARN ]: Spent 137.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-22 14:51:41,824 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:41,824 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:51:41,825 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:51:41,825 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 14:51:41,825 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:41,825 INFO ]: With dead ends: 15 [2018-06-22 14:51:41,826 INFO ]: Without dead ends: 15 [2018-06-22 14:51:41,826 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 14:51:41,827 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:51:41,830 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:51:41,830 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:51:41,830 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:51:41,830 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:51:41,831 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:41,831 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:51:41,831 INFO ]: Interpolant automaton has 9 states. [2018-06-22 14:51:41,831 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:51:41,831 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:51:41,831 INFO ]: Found error trace [2018-06-22 14:51:41,831 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:41,831 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:41,832 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 14:51:41,832 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:41,832 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:41,832 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:41,832 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:51:41,832 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:41,900 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:42,389 WARN ]: Spent 367.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 10 [2018-06-22 14:51:42,501 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:42,501 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:42,501 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:42,510 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:51:42,578 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:51:42,578 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:42,582 INFO ]: Computing forward predicates... [2018-06-22 14:51:42,954 WARN ]: Spent 258.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 16 [2018-06-22 14:51:43,076 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:43,096 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:43,096 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 14:51:43,096 INFO ]: Interpolant automaton has 10 states [2018-06-22 14:51:43,096 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 14:51:43,096 INFO ]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-06-22 14:51:43,096 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 10 states. [2018-06-22 14:51:43,298 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:43,298 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 14:51:43,299 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 14:51:43,299 INFO ]: Start accepts. Automaton has 10 states. Word has length 17 [2018-06-22 14:51:43,299 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:43,299 INFO ]: With dead ends: 17 [2018-06-22 14:51:43,299 INFO ]: Without dead ends: 17 [2018-06-22 14:51:43,300 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 14 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=48, Invalid=108, Unknown=0, NotChecked=0, Total=156 [2018-06-22 14:51:43,300 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 14:51:43,302 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 14:51:43,302 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 14:51:43,303 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 14:51:43,303 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 14:51:43,303 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:43,303 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 14:51:43,303 INFO ]: Interpolant automaton has 10 states. [2018-06-22 14:51:43,304 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 14:51:43,304 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 14:51:43,304 INFO ]: Found error trace [2018-06-22 14:51:43,304 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:43,304 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:43,305 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 14:51:43,305 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:43,305 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:43,306 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:43,306 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:43,306 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:43,366 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:43,831 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 26 [2018-06-22 14:51:43,981 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:43,981 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:43,981 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:51:43,995 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:51:44,051 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 14:51:44,052 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:44,056 INFO ]: Computing forward predicates... [2018-06-22 14:51:45,034 WARN ]: Spent 691.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 35 [2018-06-22 14:51:45,229 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 25 [2018-06-22 14:51:45,450 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:45,469 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:45,469 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-22 14:51:45,470 INFO ]: Interpolant automaton has 15 states [2018-06-22 14:51:45,470 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 14:51:45,470 INFO ]: CoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2018-06-22 14:51:45,470 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 15 states. [2018-06-22 14:51:45,952 WARN ]: Spent 464.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 56 [2018-06-22 14:51:46,201 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 38 [2018-06-22 14:51:46,573 WARN ]: Spent 355.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 33 [2018-06-22 14:51:46,999 WARN ]: Spent 401.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 51 [2018-06-22 14:51:47,355 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 57 [2018-06-22 14:51:47,375 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:47,375 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 14:51:47,376 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 14:51:47,376 INFO ]: Start accepts. Automaton has 15 states. Word has length 21 [2018-06-22 14:51:47,376 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:47,377 INFO ]: With dead ends: 21 [2018-06-22 14:51:47,377 INFO ]: Without dead ends: 21 [2018-06-22 14:51:47,377 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=105, Invalid=275, Unknown=0, NotChecked=0, Total=380 [2018-06-22 14:51:47,377 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 14:51:47,381 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 14:51:47,381 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 14:51:47,381 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 14:51:47,382 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 21 [2018-06-22 14:51:47,382 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:47,382 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 14:51:47,382 INFO ]: Interpolant automaton has 15 states. [2018-06-22 14:51:47,382 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 14:51:47,383 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 14:51:47,383 INFO ]: Found error trace [2018-06-22 14:51:47,383 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:47,383 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:47,383 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 4 times [2018-06-22 14:51:47,383 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:47,383 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:47,384 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:47,384 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:47,384 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:47,486 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:47,785 WARN ]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 14:51:48,539 WARN ]: Spent 706.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2018-06-22 14:51:49,139 WARN ]: Spent 527.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 31 [2018-06-22 14:51:49,472 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:49,472 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:51:49,472 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:49,478 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 14:51:49,565 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 14:51:49,566 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:49,572 INFO ]: Computing forward predicates... [2018-06-22 14:51:52,986 WARN ]: Spent 3.06 s on a formula simplification. DAG size of input: 95 DAG size of output: 41 [2018-06-22 14:51:53,826 WARN ]: Spent 719.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 47 [2018-06-22 14:51:54,687 WARN ]: Spent 639.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 42 [2018-06-22 14:51:55,290 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:55,310 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:51:55,310 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 14:51:55,310 INFO ]: Interpolant automaton has 20 states [2018-06-22 14:51:55,311 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 14:51:55,311 INFO ]: CoverageRelationStatistics Valid=55, Invalid=325, Unknown=0, NotChecked=0, Total=380 [2018-06-22 14:51:55,311 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 20 states. [2018-06-22 14:51:56,397 WARN ]: Spent 1.01 s on a formula simplification. DAG size of input: 95 DAG size of output: 65 [2018-06-22 14:51:56,779 WARN ]: Spent 322.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 24 [2018-06-22 14:51:57,312 WARN ]: Spent 458.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 40 [2018-06-22 14:51:57,849 WARN ]: Spent 508.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 35 [2018-06-22 14:51:58,398 WARN ]: Spent 517.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 50 [2018-06-22 14:51:59,254 WARN ]: Spent 825.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 39 [2018-06-22 14:51:59,289 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:51:59,289 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 14:51:59,290 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 14:51:59,290 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-22 14:51:59,290 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:51:59,291 INFO ]: With dead ends: 23 [2018-06-22 14:51:59,291 INFO ]: Without dead ends: 23 [2018-06-22 14:51:59,291 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 21 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 10.6s TimeCoverageRelationStatistics Valid=135, Invalid=567, Unknown=0, NotChecked=0, Total=702 [2018-06-22 14:51:59,291 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 14:51:59,294 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 14:51:59,294 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 14:51:59,295 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 14:51:59,295 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 14:51:59,295 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:51:59,295 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 14:51:59,295 INFO ]: Interpolant automaton has 20 states. [2018-06-22 14:51:59,295 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 14:51:59,296 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 14:51:59,296 INFO ]: Found error trace [2018-06-22 14:51:59,296 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:51:59,296 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:51:59,296 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 5 times [2018-06-22 14:51:59,296 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:51:59,296 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:51:59,297 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:59,297 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:51:59,297 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:51:59,394 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:51:59,951 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 36 [2018-06-22 14:52:00,078 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 35 [2018-06-22 14:52:00,286 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 36 [2018-06-22 14:52:00,782 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:00,783 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:00,783 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:52:00,793 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 14:52:00,890 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-22 14:52:00,890 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:00,896 INFO ]: Computing forward predicates... [2018-06-22 14:52:01,298 WARN ]: Spent 302.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 34 [2018-06-22 14:52:01,546 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 31 [2018-06-22 14:52:01,945 WARN ]: Spent 318.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 42 [2018-06-22 14:52:02,188 WARN ]: Spent 198.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 28 [2018-06-22 14:52:02,484 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 29 [2018-06-22 14:52:03,729 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:03,749 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:52:03,749 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 28 [2018-06-22 14:52:03,749 INFO ]: Interpolant automaton has 28 states [2018-06-22 14:52:03,750 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-22 14:52:03,750 INFO ]: CoverageRelationStatistics Valid=80, Invalid=676, Unknown=0, NotChecked=0, Total=756 [2018-06-22 14:52:03,750 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 28 states. [2018-06-22 14:52:04,719 WARN ]: Spent 907.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 87 [2018-06-22 14:52:05,077 WARN ]: Spent 294.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 49 [2018-06-22 14:52:05,607 WARN ]: Spent 490.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 57 [2018-06-22 14:52:06,267 WARN ]: Spent 484.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 54 [2018-06-22 14:52:06,699 WARN ]: Spent 394.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 55 [2018-06-22 14:52:07,035 WARN ]: Spent 290.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 60 [2018-06-22 14:52:07,721 WARN ]: Spent 622.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 79 [2018-06-22 14:52:07,771 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:52:07,771 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 14:52:07,771 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 14:52:07,771 INFO ]: Start accepts. Automaton has 28 states. Word has length 33 [2018-06-22 14:52:07,771 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:52:07,772 INFO ]: With dead ends: 25 [2018-06-22 14:52:07,772 INFO ]: Without dead ends: 25 [2018-06-22 14:52:07,772 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=205, Invalid=1055, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 14:52:07,773 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 14:52:07,776 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 14:52:07,776 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 14:52:07,776 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 14:52:07,776 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 14:52:07,777 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:52:07,777 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 14:52:07,777 INFO ]: Interpolant automaton has 28 states. [2018-06-22 14:52:07,777 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 14:52:07,777 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 14:52:07,777 INFO ]: Found error trace [2018-06-22 14:52:07,777 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:52:07,778 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:52:07,778 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 6 times [2018-06-22 14:52:07,778 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:52:07,778 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:52:07,778 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:07,778 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:52:07,778 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:52:07,903 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:08,339 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 40 [2018-06-22 14:52:08,784 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 30 [2018-06-22 14:52:09,124 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:09,124 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:52:09,124 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) [2018-06-22 14:52:09,135 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:52:09,237 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2018-06-22 14:52:09,237 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:52:09,246 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 14:52:41,287 INFO ]: Timeout while computing interpolants [2018-06-22 14:52:41,487 WARN ]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:52:41,487 WARN ]: Verification canceled [2018-06-22 14:52:41,491 WARN ]: Timeout [2018-06-22 14:52:41,492 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:52:41 BoogieIcfgContainer [2018-06-22 14:52:41,492 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:52:41,493 INFO ]: Toolchain (without parser) took 62929.35 ms. Allocated memory was 304.6 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 249.0 MB in the beginning and 1.1 GB in the end (delta: -850.7 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-22 14:52:41,494 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 268.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:52:41,494 INFO ]: ChcToBoogie took 53.74 ms. Allocated memory is still 304.6 MB. Free memory was 249.0 MB in the beginning and 247.1 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:41,495 INFO ]: Boogie Preprocessor took 46.60 ms. Allocated memory is still 304.6 MB. Free memory was 247.1 MB in the beginning and 245.1 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:41,495 INFO ]: RCFGBuilder took 283.15 ms. Allocated memory is still 304.6 MB. Free memory was 245.1 MB in the beginning and 231.0 MB in the end (delta: 14.1 MB). Peak memory consumption was 14.1 MB. Max. memory is 3.6 GB. [2018-06-22 14:52:41,495 INFO ]: TraceAbstraction took 62531.35 ms. Allocated memory was 304.6 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 231.0 MB in the beginning and 1.1 GB in the end (delta: -868.7 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-22 14:52:41,503 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 268.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.74 ms. Allocated memory is still 304.6 MB. Free memory was 249.0 MB in the beginning and 247.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 46.60 ms. Allocated memory is still 304.6 MB. Free memory was 247.1 MB in the beginning and 245.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 283.15 ms. Allocated memory is still 304.6 MB. Free memory was 245.1 MB in the beginning and 231.0 MB in the end (delta: 14.1 MB). Peak memory consumption was 14.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62531.35 ms. Allocated memory was 304.6 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 231.0 MB in the beginning and 1.1 GB in the end (delta: -868.7 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 5 quantified variables from 11 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 62.4s OverallTime, 7 OverallIterations, 8 TraceHistogramMax, 10.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 76 SDtfs, 173 SDslu, 366 SDs, 0 SdLazy, 318 SolverSat, 217 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 192 GetRequests, 85 SyntacticMatches, 7 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 344 ImplicationChecksByTransitivity, 23.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=6, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 16.6s InterpolantComputationTime, 235 NumberOfCodeBlocks, 235 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 224 ConstructedInterpolants, 0 QuantifiedInterpolants, 165092 SizeOfPredicates, 279 NumberOfNonLiveVariables, 1559 ConjunctsInSsa, 221 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 92/334 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/bk-nat.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-52-41-513.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bk-nat.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-52-41-513.csv Completed graceful shutdown