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/nested8.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:17:20,566 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:17:20,568 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:17:20,579 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:17:20,579 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:17:20,580 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:17:20,581 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:17:20,583 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:17:20,584 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:17:20,585 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:17:20,586 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:17:20,586 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:17:20,587 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:17:20,588 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:17:20,589 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:17:20,589 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:17:20,591 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:17:20,593 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:17:20,595 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:17:20,596 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:17:20,597 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:17:20,599 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:17:20,600 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:17:20,600 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:17:20,601 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:17:20,602 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:17:20,602 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:17:20,603 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:17:20,604 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:17:20,605 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:17:20,605 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:17:20,606 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:17:20,606 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:17:20,607 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:17:20,608 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:17:20,608 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 15:17:20,626 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:17:20,626 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:17:20,626 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:17:20,627 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:17:20,628 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:17:20,628 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:17:20,628 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:17:20,628 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:17:20,628 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:17:20,629 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:17:20,629 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:17:20,629 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:17:20,629 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:17:20,629 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:17:20,629 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:17:20,630 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:17:20,630 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:17:20,630 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:17:20,630 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:17:20,631 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:17:20,632 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:17:20,673 INFO ]: Repository-Root is: /tmp [2018-06-22 15:17:20,686 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:17:20,689 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:17:20,693 INFO ]: Initializing SmtParser... [2018-06-22 15:17:20,693 INFO ]: SmtParser initialized [2018-06-22 15:17:20,694 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested8.c.smt2 [2018-06-22 15:17:20,695 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 15:17:20,789 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested8.c.smt2 unknown [2018-06-22 15:17:21,060 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested8.c.smt2 [2018-06-22 15:17:21,069 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:17:21,082 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:17:21,082 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:17:21,082 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:17:21,082 INFO ]: ChcToBoogie initialized [2018-06-22 15:17:21,088 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,128 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21 Unit [2018-06-22 15:17:21,128 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:17:21,128 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:17:21,128 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:17:21,128 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:17:21,147 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,147 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,159 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,160 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,173 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,174 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,175 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (1/1) ... [2018-06-22 15:17:21,186 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:17:21,187 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:17:21,187 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:17:21,187 INFO ]: RCFGBuilder initialized [2018-06-22 15:17:21,187 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (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 15:17:21,199 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:17:21,199 INFO ]: Found specification of procedure False [2018-06-22 15:17:21,199 INFO ]: Found implementation of procedure False [2018-06-22 15:17:21,199 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:17:21,199 INFO ]: Found specification of procedure state [2018-06-22 15:17:21,199 INFO ]: Found implementation of procedure state [2018-06-22 15:17:21,199 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:17:21,199 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:17:21,199 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 15:17:21,373 INFO ]: Using library mode [2018-06-22 15:17:21,374 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:17:21 BoogieIcfgContainer [2018-06-22 15:17:21,374 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:17:21,375 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:17:21,375 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:17:21,384 INFO ]: TraceAbstraction initialized [2018-06-22 15:17:21,385 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:17:21" (1/3) ... [2018-06-22 15:17:21,385 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5b1a8725 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:17:21, skipping insertion in model container [2018-06-22 15:17:21,386 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:17:21" (2/3) ... [2018-06-22 15:17:21,386 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5b1a8725 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:17:21, skipping insertion in model container [2018-06-22 15:17:21,386 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:17:21" (3/3) ... [2018-06-22 15:17:21,387 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:17:21,397 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:17:21,407 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:17:21,445 INFO ]: Using default assertion order modulation [2018-06-22 15:17:21,445 INFO ]: Interprodecural is true [2018-06-22 15:17:21,445 INFO ]: Hoare is false [2018-06-22 15:17:21,445 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:17:21,445 INFO ]: Backedges is TWOTRACK [2018-06-22 15:17:21,445 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:17:21,445 INFO ]: Difference is false [2018-06-22 15:17:21,445 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:17:21,445 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:17:21,458 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:17:21,467 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:17:21,467 INFO ]: Found error trace [2018-06-22 15:17:21,468 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:21,468 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:21,474 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:17:21,476 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:21,477 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:21,509 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:21,510 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:17:21,510 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:21,536 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:21,653 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:17:21,664 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:17:21,665 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:17:21,666 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:17:21,696 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:17:21,696 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:17:21,699 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:17:21,804 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:21,804 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:17:21,806 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:17:21,807 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:17:21,807 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:21,817 INFO ]: With dead ends: 13 [2018-06-22 15:17:21,817 INFO ]: Without dead ends: 13 [2018-06-22 15:17:21,818 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 15:17:21,830 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:17:21,849 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:17:21,850 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:17:21,850 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:17:21,851 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:17:21,851 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:21,851 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:17:21,851 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:17:21,851 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:17:21,852 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:17:21,852 INFO ]: Found error trace [2018-06-22 15:17:21,852 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:21,853 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:21,853 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:17:21,853 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:21,853 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:21,854 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:21,854 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:17:21,854 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:21,902 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:22,156 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:17:22,156 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:22,156 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:17:22,171 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:17:22,206 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:22,214 INFO ]: Computing forward predicates... [2018-06-22 15:17:22,553 WARN ]: Spent 170.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 15:17:22,736 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:17:22,756 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:22,756 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 15:17:22,756 INFO ]: Interpolant automaton has 9 states [2018-06-22 15:17:22,757 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 15:17:22,757 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 15:17:22,757 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 15:17:22,981 WARN ]: Spent 187.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:17:23,207 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:23,207 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:17:23,208 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:17:23,208 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 15:17:23,208 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:23,209 INFO ]: With dead ends: 15 [2018-06-22 15:17:23,209 INFO ]: Without dead ends: 15 [2018-06-22 15:17:23,210 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 15:17:23,210 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:17:23,212 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:17:23,212 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:17:23,213 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:17:23,213 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:17:23,213 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:23,213 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:17:23,213 INFO ]: Interpolant automaton has 9 states. [2018-06-22 15:17:23,213 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:17:23,214 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:17:23,214 INFO ]: Found error trace [2018-06-22 15:17:23,214 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:23,214 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:23,214 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:17:23,214 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:23,214 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:23,215 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:23,215 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:17:23,215 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:23,281 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:23,647 WARN ]: Spent 185.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 9 [2018-06-22 15:17:23,807 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:17:23,807 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:23,807 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 15:17:23,816 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:17:23,867 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:17:23,867 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:23,870 INFO ]: Computing forward predicates... [2018-06-22 15:17:24,271 WARN ]: Spent 354.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-22 15:17:24,784 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:17:24,803 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:24,803 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:17:24,803 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:17:24,803 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:17:24,804 INFO ]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:17:24,804 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:17:24,950 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2018-06-22 15:17:25,266 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:25,266 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:17:25,266 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:17:25,266 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:17:25,266 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:25,267 INFO ]: With dead ends: 17 [2018-06-22 15:17:25,267 INFO ]: Without dead ends: 17 [2018-06-22 15:17:25,267 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=50, Invalid=160, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:17:25,268 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:17:25,271 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:17:25,271 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:17:25,271 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:17:25,271 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:17:25,272 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:25,272 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:17:25,272 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:17:25,272 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:17:25,272 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:17:25,272 INFO ]: Found error trace [2018-06-22 15:17:25,272 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:25,273 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:25,273 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:17:25,273 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:25,273 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:25,274 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:25,274 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:17:25,274 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:25,325 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:25,687 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:17:25,687 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:25,687 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 15:17:25,703 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:17:25,750 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:17:25,750 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:25,754 INFO ]: Computing forward predicates... [2018-06-22 15:17:26,207 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:17:26,232 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:26,232 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-22 15:17:26,232 INFO ]: Interpolant automaton has 13 states [2018-06-22 15:17:26,232 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 15:17:26,232 INFO ]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:17:26,232 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 13 states. [2018-06-22 15:17:26,360 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 28 [2018-06-22 15:17:26,712 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 26 [2018-06-22 15:17:26,732 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:26,732 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:17:26,733 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:17:26,733 INFO ]: Start accepts. Automaton has 13 states. Word has length 21 [2018-06-22 15:17:26,733 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:26,733 INFO ]: With dead ends: 19 [2018-06-22 15:17:26,733 INFO ]: Without dead ends: 19 [2018-06-22 15:17:26,734 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=74, Invalid=198, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:17:26,734 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:17:26,737 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:17:26,737 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:17:26,738 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:17:26,738 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:17:26,738 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:26,738 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:17:26,738 INFO ]: Interpolant automaton has 13 states. [2018-06-22 15:17:26,738 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:17:26,739 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:17:26,739 INFO ]: Found error trace [2018-06-22 15:17:26,739 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:26,739 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:26,739 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:17:26,739 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:26,739 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:26,740 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:26,740 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:17:26,740 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:26,776 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:27,079 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:17:27,079 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:27,079 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 15:17:27,090 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:17:27,142 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:17:27,142 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:27,147 INFO ]: Computing forward predicates... [2018-06-22 15:17:27,539 WARN ]: Spent 339.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 24 [2018-06-22 15:17:27,818 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:17:27,839 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:27,839 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-22 15:17:27,839 INFO ]: Interpolant automaton has 16 states [2018-06-22 15:17:27,839 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 15:17:27,839 INFO ]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2018-06-22 15:17:27,840 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 16 states. [2018-06-22 15:17:28,117 WARN ]: Spent 251.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 43 [2018-06-22 15:17:28,252 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 21 [2018-06-22 15:17:28,442 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 29 [2018-06-22 15:17:28,621 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 31 [2018-06-22 15:17:28,914 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 35 [2018-06-22 15:17:28,944 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:28,944 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:17:28,945 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:17:28,945 INFO ]: Start accepts. Automaton has 16 states. Word has length 25 [2018-06-22 15:17:28,945 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:28,945 INFO ]: With dead ends: 21 [2018-06-22 15:17:28,945 INFO ]: Without dead ends: 21 [2018-06-22 15:17:28,946 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=100, Invalid=362, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:17:28,946 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:17:28,949 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:17:28,950 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:17:28,950 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:17:28,950 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:17:28,950 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:28,950 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:17:28,950 INFO ]: Interpolant automaton has 16 states. [2018-06-22 15:17:28,950 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:17:28,951 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:17:28,951 INFO ]: Found error trace [2018-06-22 15:17:28,951 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:28,951 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:28,952 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:17:28,952 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:28,952 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:28,953 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:28,953 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:17:28,953 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:29,051 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:29,701 WARN ]: Spent 476.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:17:30,481 WARN ]: Spent 701.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 31 [2018-06-22 15:17:30,587 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 26 [2018-06-22 15:17:30,819 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:17:30,820 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:30,820 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 15:17:30,827 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:17:30,868 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:17:30,868 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:30,872 INFO ]: Computing forward predicates... [2018-06-22 15:17:32,632 WARN ]: Spent 1.36 s on a formula simplification. DAG size of input: 35 DAG size of output: 30 [2018-06-22 15:17:32,813 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 22 [2018-06-22 15:17:33,019 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:17:33,038 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:33,038 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 18 [2018-06-22 15:17:33,039 INFO ]: Interpolant automaton has 18 states [2018-06-22 15:17:33,039 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 15:17:33,039 INFO ]: CoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2018-06-22 15:17:33,039 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 18 states. [2018-06-22 15:17:33,606 WARN ]: Spent 533.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 47 [2018-06-22 15:17:33,735 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 25 [2018-06-22 15:17:33,887 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 27 [2018-06-22 15:17:34,085 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 33 [2018-06-22 15:17:34,375 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 36 [2018-06-22 15:17:34,630 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 45 [2018-06-22 15:17:34,654 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:34,654 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:17:34,655 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:17:34,655 INFO ]: Start accepts. Automaton has 18 states. Word has length 29 [2018-06-22 15:17:34,655 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:34,655 INFO ]: With dead ends: 23 [2018-06-22 15:17:34,655 INFO ]: Without dead ends: 23 [2018-06-22 15:17:34,656 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 21 SyntacticMatches, 5 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=129, Invalid=423, Unknown=0, NotChecked=0, Total=552 [2018-06-22 15:17:34,656 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:17:34,659 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:17:34,659 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:17:34,660 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:17:34,660 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:17:34,660 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:34,660 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:17:34,660 INFO ]: Interpolant automaton has 18 states. [2018-06-22 15:17:34,660 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:17:34,661 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:17:34,661 INFO ]: Found error trace [2018-06-22 15:17:34,661 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:34,661 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:34,661 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:17:34,661 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:34,661 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:34,662 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:34,662 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:17:34,662 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:34,746 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:35,462 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:17:35,463 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:35,463 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 15:17:35,477 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 15:17:35,574 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:17:35,574 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:35,579 INFO ]: Computing forward predicates... [2018-06-22 15:17:36,074 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 36 [2018-06-22 15:17:36,261 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 28 [2018-06-22 15:17:37,251 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:17:37,347 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:17:37,379 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:37,379 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2018-06-22 15:17:37,379 INFO ]: Interpolant automaton has 27 states [2018-06-22 15:17:37,379 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 15:17:37,380 INFO ]: CoverageRelationStatistics Valid=84, Invalid=618, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:17:37,380 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 27 states. [2018-06-22 15:17:38,004 WARN ]: Spent 459.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 69 [2018-06-22 15:17:38,436 WARN ]: Spent 279.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 42 [2018-06-22 15:17:38,730 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 49 [2018-06-22 15:17:38,976 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 45 [2018-06-22 15:17:39,213 WARN ]: Spent 202.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 40 [2018-06-22 15:17:39,625 WARN ]: Spent 317.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 44 [2018-06-22 15:17:39,677 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:39,677 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:17:39,678 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:17:39,678 INFO ]: Start accepts. Automaton has 27 states. Word has length 33 [2018-06-22 15:17:39,679 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:39,679 INFO ]: With dead ends: 25 [2018-06-22 15:17:39,679 INFO ]: Without dead ends: 25 [2018-06-22 15:17:39,680 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=203, Invalid=987, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:17:39,680 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:17:39,683 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:17:39,683 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:17:39,684 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:17:39,684 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:17:39,684 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:39,684 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:17:39,684 INFO ]: Interpolant automaton has 27 states. [2018-06-22 15:17:39,684 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:17:39,685 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:17:39,685 INFO ]: Found error trace [2018-06-22 15:17:39,685 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:39,685 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:39,685 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:17:39,685 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:39,685 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:39,686 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:39,686 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:17:39,686 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:39,741 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:39,974 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 15:17:40,546 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:17:40,546 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:40,546 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 15:17:40,554 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:17:40,601 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:40,606 INFO ]: Computing forward predicates... [2018-06-22 15:17:41,294 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 36 [2018-06-22 15:17:41,479 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 28 [2018-06-22 15:17:42,191 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:17:42,211 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:42,211 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 31 [2018-06-22 15:17:42,211 INFO ]: Interpolant automaton has 31 states [2018-06-22 15:17:42,211 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-22 15:17:42,212 INFO ]: CoverageRelationStatistics Valid=99, Invalid=831, Unknown=0, NotChecked=0, Total=930 [2018-06-22 15:17:42,212 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 31 states. [2018-06-22 15:17:42,799 WARN ]: Spent 540.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 75 [2018-06-22 15:17:43,220 WARN ]: Spent 248.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 42 [2018-06-22 15:17:43,490 WARN ]: Spent 236.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 47 [2018-06-22 15:17:43,748 WARN ]: Spent 230.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 45 [2018-06-22 15:17:43,984 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 38 [2018-06-22 15:17:44,278 WARN ]: Spent 260.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 36 [2018-06-22 15:17:44,867 WARN ]: Spent 543.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 68 [2018-06-22 15:17:44,899 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:17:44,899 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:17:44,899 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:17:44,899 INFO ]: Start accepts. Automaton has 31 states. Word has length 37 [2018-06-22 15:17:44,900 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:17:44,900 INFO ]: With dead ends: 27 [2018-06-22 15:17:44,900 INFO ]: Without dead ends: 27 [2018-06-22 15:17:44,901 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 219 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=257, Invalid=1303, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 15:17:44,901 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:17:44,904 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:17:44,904 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:17:44,905 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:17:44,905 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:17:44,905 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:17:44,905 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:17:44,905 INFO ]: Interpolant automaton has 31 states. [2018-06-22 15:17:44,905 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:17:44,906 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:17:44,906 INFO ]: Found error trace [2018-06-22 15:17:44,906 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:17:44,906 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:17:44,906 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-22 15:17:44,906 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:17:44,906 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:17:44,907 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:44,907 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:17:44,907 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:17:45,093 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:45,864 WARN ]: Spent 475.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 23 [2018-06-22 15:17:46,630 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:17:46,630 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:17:46,630 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:17:46,636 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:17:46,690 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:17:46,690 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:17:46,697 INFO ]: Computing forward predicates... [2018-06-22 15:17:47,525 WARN ]: Spent 653.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 68 [2018-06-22 15:17:47,951 WARN ]: Spent 369.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 44 [2018-06-22 15:17:48,135 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 44 [2018-06-22 15:17:48,365 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 32 [2018-06-22 15:17:48,540 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 36 [2018-06-22 15:17:48,759 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 27 [2018-06-22 15:17:49,771 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 15:17:57,221 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:17:57,242 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:17:57,242 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 37 [2018-06-22 15:17:57,242 INFO ]: Interpolant automaton has 37 states [2018-06-22 15:17:57,242 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-22 15:17:57,243 INFO ]: CoverageRelationStatistics Valid=109, Invalid=1223, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 15:17:57,243 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 37 states. [2018-06-22 15:17:58,734 WARN ]: Spent 1.35 s on a formula simplification. DAG size of input: 201 DAG size of output: 141 [2018-06-22 15:17:59,457 WARN ]: Spent 617.00 ms on a formula simplification. DAG size of input: 204 DAG size of output: 72 [2018-06-22 15:18:00,270 WARN ]: Spent 681.00 ms on a formula simplification. DAG size of input: 208 DAG size of output: 61 [2018-06-22 15:18:01,112 WARN ]: Spent 743.00 ms on a formula simplification. DAG size of input: 211 DAG size of output: 84 [2018-06-22 15:18:01,921 WARN ]: Spent 735.00 ms on a formula simplification. DAG size of input: 209 DAG size of output: 68 [2018-06-22 15:18:02,823 WARN ]: Spent 810.00 ms on a formula simplification. DAG size of input: 211 DAG size of output: 72 [2018-06-22 15:18:03,786 WARN ]: Spent 900.00 ms on a formula simplification. DAG size of input: 214 DAG size of output: 82 [2018-06-22 15:18:04,804 WARN ]: Spent 951.00 ms on a formula simplification. DAG size of input: 215 DAG size of output: 77 [2018-06-22 15:18:06,180 WARN ]: Spent 1.29 s on a formula simplification. DAG size of input: 205 DAG size of output: 120 [2018-06-22 15:18:06,238 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:06,238 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:18:06,239 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:18:06,239 INFO ]: Start accepts. Automaton has 37 states. Word has length 41 [2018-06-22 15:18:06,239 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:06,240 INFO ]: With dead ends: 29 [2018-06-22 15:18:06,240 INFO ]: Without dead ends: 29 [2018-06-22 15:18:06,240 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 13.3s TimeCoverageRelationStatistics Valid=307, Invalid=1763, Unknown=0, NotChecked=0, Total=2070 [2018-06-22 15:18:06,240 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:18:06,244 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:18:06,244 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:18:06,245 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:18:06,245 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:18:06,245 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:06,245 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:18:06,245 INFO ]: Interpolant automaton has 37 states. [2018-06-22 15:18:06,245 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:18:06,246 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:18:06,246 INFO ]: Found error trace [2018-06-22 15:18:06,246 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:06,246 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:06,246 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-22 15:18:06,246 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:06,246 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:06,247 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:06,247 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:06,247 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:06,359 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:07,186 WARN ]: Spent 502.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 21 [2018-06-22 15:18:07,401 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 67 DAG size of output: 53 [2018-06-22 15:18:07,561 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 49 [2018-06-22 15:18:07,689 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 47 [2018-06-22 15:18:07,829 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 38 [2018-06-22 15:18:08,057 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 43 [2018-06-22 15:18:08,892 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:18:08,892 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:18:08,892 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:18:08,897 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:18:08,983 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:18:08,983 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:08,998 INFO ]: Computing forward predicates... [2018-06-22 15:18:09,540 WARN ]: Spent 329.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 46 [2018-06-22 15:18:09,798 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 37 [2018-06-22 15:18:09,964 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 35 [2018-06-22 15:18:10,133 WARN ]: Spent 123.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 42 [2018-06-22 15:18:10,337 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 36 [2018-06-22 15:18:10,535 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 31 [2018-06-22 15:18:12,592 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:18:12,611 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:18:12,611 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 41 [2018-06-22 15:18:12,612 INFO ]: Interpolant automaton has 41 states [2018-06-22 15:18:12,612 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 15:18:12,612 INFO ]: CoverageRelationStatistics Valid=137, Invalid=1503, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:18:12,612 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 41 states. [2018-06-22 15:18:14,360 WARN ]: Spent 1.67 s on a formula simplification. DAG size of input: 200 DAG size of output: 145 [2018-06-22 15:18:14,893 WARN ]: Spent 415.00 ms on a formula simplification. DAG size of input: 193 DAG size of output: 48 [2018-06-22 15:18:15,555 WARN ]: Spent 602.00 ms on a formula simplification. DAG size of input: 195 DAG size of output: 78 [2018-06-22 15:18:16,322 WARN ]: Spent 701.00 ms on a formula simplification. DAG size of input: 198 DAG size of output: 82 [2018-06-22 15:18:17,085 WARN ]: Spent 698.00 ms on a formula simplification. DAG size of input: 198 DAG size of output: 81 [2018-06-22 15:18:17,743 WARN ]: Spent 592.00 ms on a formula simplification. DAG size of input: 198 DAG size of output: 78 [2018-06-22 15:18:18,492 WARN ]: Spent 684.00 ms on a formula simplification. DAG size of input: 205 DAG size of output: 86 [2018-06-22 15:18:19,514 WARN ]: Spent 955.00 ms on a formula simplification. DAG size of input: 210 DAG size of output: 87 [2018-06-22 15:18:20,264 WARN ]: Spent 670.00 ms on a formula simplification. DAG size of input: 202 DAG size of output: 69 [2018-06-22 15:18:21,759 WARN ]: Spent 1.41 s on a formula simplification. DAG size of input: 202 DAG size of output: 124 [2018-06-22 15:18:21,821 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:18:21,821 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:18:21,822 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:18:21,822 INFO ]: Start accepts. Automaton has 41 states. Word has length 45 [2018-06-22 15:18:21,822 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:18:21,823 INFO ]: With dead ends: 31 [2018-06-22 15:18:21,823 INFO ]: Without dead ends: 31 [2018-06-22 15:18:21,823 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 380 ImplicationChecksByTransitivity, 13.3s TimeCoverageRelationStatistics Valid=389, Invalid=2263, Unknown=0, NotChecked=0, Total=2652 [2018-06-22 15:18:21,823 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:18:21,827 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:18:21,827 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:18:21,828 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:18:21,828 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:18:21,828 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:18:21,828 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:18:21,828 INFO ]: Interpolant automaton has 41 states. [2018-06-22 15:18:21,828 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:18:21,829 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:18:21,829 INFO ]: Found error trace [2018-06-22 15:18:21,829 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:18:21,829 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:18:21,829 INFO ]: Analyzing trace with hash 352352522, now seen corresponding path program 10 times [2018-06-22 15:18:21,829 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:18:21,829 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:18:21,830 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:21,830 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:18:21,830 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:18:21,976 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:18:22,253 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 15:18:22,546 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 23 Received shutdown request... [2018-06-22 15:18:22,572 WARN ]: Removed 11 from assertion stack [2018-06-22 15:18:22,572 WARN ]: Verification canceled [2018-06-22 15:18:22,577 WARN ]: Timeout [2018-06-22 15:18:22,577 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:18:22 BoogieIcfgContainer [2018-06-22 15:18:22,577 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:18:22,579 INFO ]: Toolchain (without parser) took 61507.84 ms. Allocated memory was 302.5 MB in the beginning and 817.9 MB in the end (delta: 515.4 MB). Free memory was 255.1 MB in the beginning and 531.4 MB in the end (delta: -276.3 MB). Peak memory consumption was 239.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:18:22,579 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 302.5 MB. Free memory is still 268.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:18:22,580 INFO ]: ChcToBoogie took 45.83 ms. Allocated memory is still 302.5 MB. Free memory was 255.1 MB in the beginning and 253.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 15:18:22,580 INFO ]: Boogie Preprocessor took 57.63 ms. Allocated memory is still 302.5 MB. Free memory was 253.1 MB in the beginning and 251.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:18:22,580 INFO ]: RCFGBuilder took 187.34 ms. Allocated memory is still 302.5 MB. Free memory was 251.0 MB in the beginning and 242.0 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:18:22,581 INFO ]: TraceAbstraction took 61201.43 ms. Allocated memory was 302.5 MB in the beginning and 817.9 MB in the end (delta: 515.4 MB). Free memory was 241.0 MB in the beginning and 531.4 MB in the end (delta: -290.4 MB). Peak memory consumption was 225.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:18:22,590 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 302.5 MB. Free memory is still 268.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 45.83 ms. Allocated memory is still 302.5 MB. Free memory was 255.1 MB in the beginning and 253.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 57.63 ms. Allocated memory is still 302.5 MB. Free memory was 253.1 MB in the beginning and 251.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 187.34 ms. Allocated memory is still 302.5 MB. Free memory was 251.0 MB in the beginning and 242.0 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61201.43 ms. Allocated memory was 302.5 MB in the beginning and 817.9 MB in the end (delta: 515.4 MB). Free memory was 241.0 MB in the beginning and 531.4 MB in the end (delta: -290.4 MB). Peak memory consumption was 225.0 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 50 with TraceHistMax 11, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 43. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.1s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 27.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 138 SDtfs, 580 SDslu, 1053 SDs, 0 SdLazy, 944 SolverSat, 701 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 442 GetRequests, 182 SyntacticMatches, 13 SemanticMatches, 247 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1246 ImplicationChecksByTransitivity, 44.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred in iteration=10, 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, 10 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 31.1s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 2747224 SizeOfPredicates, 673 NumberOfNonLiveVariables, 2268 ConjunctsInSsa, 486 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 330/1230 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/nested8.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-18-22-604.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nested8.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-18-22-604.csv Completed graceful shutdown