java -Xss4m -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_Goto.epf -i /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 10:13:56,476 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 10:13:56,478 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 10:13:56,493 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 10:13:56,493 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 10:13:56,494 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 10:13:56,498 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 10:13:56,500 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 10:13:56,502 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 10:13:56,504 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 10:13:56,505 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 10:13:56,505 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 10:13:56,506 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 10:13:56,507 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 10:13:56,508 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 10:13:56,512 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 10:13:56,514 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 10:13:56,521 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 10:13:56,522 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 10:13:56,523 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 10:13:56,524 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 10:13:56,527 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 10:13:56,527 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 10:13:56,527 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 10:13:56,528 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 10:13:56,529 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 10:13:56,530 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 10:13:56,531 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 10:13:56,532 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 10:13:56,532 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 10:13:56,532 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 10:13:56,533 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 10:13:56,533 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 10:13:56,534 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 10:13:56,535 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 10:13:56,535 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 10:13:56,548 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 10:13:56,548 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 10:13:56,549 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 10:13:56,549 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 10:13:56,550 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 10:13:56,550 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 10:13:56,550 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 10:13:56,550 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 10:13:56,551 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 10:13:56,551 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 10:13:56,551 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 10:13:56,551 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 10:13:56,551 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 10:13:56,552 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 10:13:56,552 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 10:13:56,552 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 10:13:56,552 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 10:13:56,552 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 10:13:56,553 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 10:13:56,553 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 10:13:56,553 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 10:13:56,554 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 10:13:56,554 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 10:13:56,608 INFO ]: Repository-Root is: /tmp [2018-06-25 10:13:56,625 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 10:13:56,630 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 10:13:56,632 INFO ]: Initializing SmtParser... [2018-06-25 10:13:56,632 INFO ]: SmtParser initialized [2018-06-25 10:13:56,633 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 [2018-06-25 10:13:56,634 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-25 10:13:56,726 INFO ]: Executing SMT file /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 unknown de.uni_freiburg.informatik.ultimate.plugins.generator.treeautomizer.parsing.HornClauseParserScript$1@7b425343 [2018-06-25 10:13:56,975 INFO ]: Succesfully executed SMT file /storage/chc-comp/llreve-bench/smt2/rec__triangular.smt2 [2018-06-25 10:13:56,979 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 10:13:56,985 INFO ]: Walking toolchain with 4 elements. [2018-06-25 10:13:56,985 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 10:13:56,985 INFO ]: Initializing ChcToBoogie... [2018-06-25 10:13:56,985 INFO ]: ChcToBoogie initialized [2018-06-25 10:13:56,988 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 10:13:56" (1/1) ... [2018-06-25 10:13:57,044 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57 Unit [2018-06-25 10:13:57,044 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 10:13:57,045 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 10:13:57,045 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 10:13:57,045 INFO ]: Boogie Preprocessor initialized [2018-06-25 10:13:57,065 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,065 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,070 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,071 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,076 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,079 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,085 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (1/1) ... [2018-06-25 10:13:57,087 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 10:13:57,088 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 10:13:57,088 INFO ]: Initializing RCFGBuilder... [2018-06-25 10:13:57,088 INFO ]: RCFGBuilder initialized [2018-06-25 10:13:57,088 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (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-25 10:13:57,115 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 10:13:57,115 INFO ]: Found specification of procedure gotoProc [2018-06-25 10:13:57,115 INFO ]: Found implementation of procedure gotoProc [2018-06-25 10:13:57,115 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 10:13:57,115 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 10:13:57,115 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-25 10:13:57,517 INFO ]: Using library mode [2018-06-25 10:13:57,517 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 10:13:57 BoogieIcfgContainer [2018-06-25 10:13:57,518 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 10:13:57,521 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 10:13:57,521 INFO ]: Initializing TraceAbstraction... [2018-06-25 10:13:57,524 INFO ]: TraceAbstraction initialized [2018-06-25 10:13:57,524 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 10:13:56" (1/3) ... [2018-06-25 10:13:57,525 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c6199c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 10:13:57, skipping insertion in model container [2018-06-25 10:13:57,525 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 10:13:57" (2/3) ... [2018-06-25 10:13:57,525 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c6199c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 10:13:57, skipping insertion in model container [2018-06-25 10:13:57,525 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 10:13:57" (3/3) ... [2018-06-25 10:13:57,527 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 10:13:57,536 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 10:13:57,545 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 10:13:57,603 INFO ]: Using default assertion order modulation [2018-06-25 10:13:57,603 INFO ]: Interprodecural is true [2018-06-25 10:13:57,603 INFO ]: Hoare is false [2018-06-25 10:13:57,604 INFO ]: Compute interpolants for FPandBP [2018-06-25 10:13:57,604 INFO ]: Backedges is TWOTRACK [2018-06-25 10:13:57,604 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 10:13:57,604 INFO ]: Difference is false [2018-06-25 10:13:57,604 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 10:13:57,604 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 10:13:57,623 INFO ]: Start isEmpty. Operand 28 states. [2018-06-25 10:13:57,639 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 10:13:57,639 INFO ]: Found error trace [2018-06-25 10:13:57,641 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:13:57,641 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:13:57,647 INFO ]: Analyzing trace with hash 1651176972, now seen corresponding path program 1 times [2018-06-25 10:13:57,649 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:13:57,650 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:13:57,694 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:57,694 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:13:57,694 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:57,721 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:13:57,782 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 10:13:57,784 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:13:57,784 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 10:13:57,785 INFO ]: Interpolant automaton has 4 states [2018-06-25 10:13:57,795 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 10:13:57,795 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 10:13:57,797 INFO ]: Start difference. First operand 28 states. Second operand 4 states. [2018-06-25 10:13:58,324 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:13:58,324 INFO ]: Finished difference Result 49 states and 79 transitions. [2018-06-25 10:13:58,326 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 10:13:58,327 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-25 10:13:58,327 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:13:58,350 INFO ]: With dead ends: 49 [2018-06-25 10:13:58,350 INFO ]: Without dead ends: 49 [2018-06-25 10:13:58,352 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 10:13:58,374 INFO ]: Start minimizeSevpa. Operand 49 states. [2018-06-25 10:13:58,414 INFO ]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-06-25 10:13:58,417 INFO ]: Start removeUnreachable. Operand 49 states. [2018-06-25 10:13:58,422 INFO ]: Finished removeUnreachable. Reduced from 49 states to 49 states and 79 transitions. [2018-06-25 10:13:58,428 INFO ]: Start accepts. Automaton has 49 states and 79 transitions. Word has length 7 [2018-06-25 10:13:58,428 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:13:58,428 INFO ]: Abstraction has 49 states and 79 transitions. [2018-06-25 10:13:58,428 INFO ]: Interpolant automaton has 4 states. [2018-06-25 10:13:58,428 INFO ]: Start isEmpty. Operand 49 states and 79 transitions. [2018-06-25 10:13:58,430 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 10:13:58,430 INFO ]: Found error trace [2018-06-25 10:13:58,430 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:13:58,430 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:13:58,430 INFO ]: Analyzing trace with hash 1902538503, now seen corresponding path program 1 times [2018-06-25 10:13:58,430 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:13:58,430 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:13:58,432 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:58,432 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:13:58,432 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:58,436 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:13:58,591 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 10:13:58,591 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:13:58,591 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 10:13:58,593 INFO ]: Interpolant automaton has 4 states [2018-06-25 10:13:58,593 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 10:13:58,593 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 10:13:58,593 INFO ]: Start difference. First operand 49 states and 79 transitions. Second operand 4 states. [2018-06-25 10:13:58,872 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:13:58,873 INFO ]: Finished difference Result 72 states and 117 transitions. [2018-06-25 10:13:58,873 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 10:13:58,873 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-25 10:13:58,873 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:13:58,876 INFO ]: With dead ends: 72 [2018-06-25 10:13:58,876 INFO ]: Without dead ends: 72 [2018-06-25 10:13:58,879 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 10:13:58,879 INFO ]: Start minimizeSevpa. Operand 72 states. [2018-06-25 10:13:58,890 INFO ]: Finished minimizeSevpa. Reduced states from 72 to 72. [2018-06-25 10:13:58,890 INFO ]: Start removeUnreachable. Operand 72 states. [2018-06-25 10:13:58,893 INFO ]: Finished removeUnreachable. Reduced from 72 states to 72 states and 117 transitions. [2018-06-25 10:13:58,894 INFO ]: Start accepts. Automaton has 72 states and 117 transitions. Word has length 9 [2018-06-25 10:13:58,894 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:13:58,894 INFO ]: Abstraction has 72 states and 117 transitions. [2018-06-25 10:13:58,894 INFO ]: Interpolant automaton has 4 states. [2018-06-25 10:13:58,894 INFO ]: Start isEmpty. Operand 72 states and 117 transitions. [2018-06-25 10:13:58,894 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 10:13:58,894 INFO ]: Found error trace [2018-06-25 10:13:58,894 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:13:58,895 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:13:58,895 INFO ]: Analyzing trace with hash -883072120, now seen corresponding path program 1 times [2018-06-25 10:13:58,895 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:13:58,895 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:13:58,896 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:58,896 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:13:58,896 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:58,902 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:13:58,929 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 10:13:58,929 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:13:58,929 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 10:13:58,930 INFO ]: Interpolant automaton has 4 states [2018-06-25 10:13:58,930 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 10:13:58,930 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 10:13:58,930 INFO ]: Start difference. First operand 72 states and 117 transitions. Second operand 4 states. [2018-06-25 10:13:59,066 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:13:59,066 INFO ]: Finished difference Result 95 states and 155 transitions. [2018-06-25 10:13:59,067 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 10:13:59,067 INFO ]: Start accepts. Automaton has 4 states. Word has length 10 [2018-06-25 10:13:59,067 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:13:59,070 INFO ]: With dead ends: 95 [2018-06-25 10:13:59,070 INFO ]: Without dead ends: 95 [2018-06-25 10:13:59,070 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 10:13:59,070 INFO ]: Start minimizeSevpa. Operand 95 states. [2018-06-25 10:13:59,082 INFO ]: Finished minimizeSevpa. Reduced states from 95 to 95. [2018-06-25 10:13:59,082 INFO ]: Start removeUnreachable. Operand 95 states. [2018-06-25 10:13:59,085 INFO ]: Finished removeUnreachable. Reduced from 95 states to 95 states and 155 transitions. [2018-06-25 10:13:59,085 INFO ]: Start accepts. Automaton has 95 states and 155 transitions. Word has length 10 [2018-06-25 10:13:59,085 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:13:59,085 INFO ]: Abstraction has 95 states and 155 transitions. [2018-06-25 10:13:59,085 INFO ]: Interpolant automaton has 4 states. [2018-06-25 10:13:59,085 INFO ]: Start isEmpty. Operand 95 states and 155 transitions. [2018-06-25 10:13:59,086 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 10:13:59,086 INFO ]: Found error trace [2018-06-25 10:13:59,086 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:13:59,086 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:13:59,086 INFO ]: Analyzing trace with hash -850036425, now seen corresponding path program 1 times [2018-06-25 10:13:59,086 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:13:59,086 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:13:59,087 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:59,087 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:13:59,087 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:59,098 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:13:59,160 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 10:13:59,160 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:13:59,160 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 10:13:59,161 INFO ]: Interpolant automaton has 3 states [2018-06-25 10:13:59,161 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 10:13:59,161 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 10:13:59,161 INFO ]: Start difference. First operand 95 states and 155 transitions. Second operand 3 states. [2018-06-25 10:13:59,314 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:13:59,314 INFO ]: Finished difference Result 167 states and 312 transitions. [2018-06-25 10:13:59,314 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 10:13:59,314 INFO ]: Start accepts. Automaton has 3 states. Word has length 11 [2018-06-25 10:13:59,315 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:13:59,321 INFO ]: With dead ends: 167 [2018-06-25 10:13:59,321 INFO ]: Without dead ends: 167 [2018-06-25 10:13:59,321 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 10:13:59,321 INFO ]: Start minimizeSevpa. Operand 167 states. [2018-06-25 10:13:59,344 INFO ]: Finished minimizeSevpa. Reduced states from 167 to 99. [2018-06-25 10:13:59,344 INFO ]: Start removeUnreachable. Operand 99 states. [2018-06-25 10:13:59,346 INFO ]: Finished removeUnreachable. Reduced from 99 states to 99 states and 167 transitions. [2018-06-25 10:13:59,346 INFO ]: Start accepts. Automaton has 99 states and 167 transitions. Word has length 11 [2018-06-25 10:13:59,346 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:13:59,346 INFO ]: Abstraction has 99 states and 167 transitions. [2018-06-25 10:13:59,346 INFO ]: Interpolant automaton has 3 states. [2018-06-25 10:13:59,347 INFO ]: Start isEmpty. Operand 99 states and 167 transitions. [2018-06-25 10:13:59,348 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-25 10:13:59,348 INFO ]: Found error trace [2018-06-25 10:13:59,348 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:13:59,348 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:13:59,348 INFO ]: Analyzing trace with hash -1450575790, now seen corresponding path program 1 times [2018-06-25 10:13:59,348 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:13:59,349 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:13:59,349 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:59,349 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:13:59,349 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:13:59,361 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:13:59,521 INFO ]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-25 10:13:59,521 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:13:59,521 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-06-25 10:13:59,521 INFO ]: Interpolant automaton has 6 states [2018-06-25 10:13:59,522 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 10:13:59,522 INFO ]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-06-25 10:13:59,522 INFO ]: Start difference. First operand 99 states and 167 transitions. Second operand 6 states. [2018-06-25 10:14:00,000 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:00,000 INFO ]: Finished difference Result 209 states and 481 transitions. [2018-06-25 10:14:00,001 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 10:14:00,001 INFO ]: Start accepts. Automaton has 6 states. Word has length 19 [2018-06-25 10:14:00,001 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:00,005 INFO ]: With dead ends: 209 [2018-06-25 10:14:00,005 INFO ]: Without dead ends: 209 [2018-06-25 10:14:00,006 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-25 10:14:00,006 INFO ]: Start minimizeSevpa. Operand 209 states. [2018-06-25 10:14:00,066 INFO ]: Finished minimizeSevpa. Reduced states from 209 to 103. [2018-06-25 10:14:00,066 INFO ]: Start removeUnreachable. Operand 103 states. [2018-06-25 10:14:00,072 INFO ]: Finished removeUnreachable. Reduced from 103 states to 103 states and 171 transitions. [2018-06-25 10:14:00,072 INFO ]: Start accepts. Automaton has 103 states and 171 transitions. Word has length 19 [2018-06-25 10:14:00,073 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:00,073 INFO ]: Abstraction has 103 states and 171 transitions. [2018-06-25 10:14:00,073 INFO ]: Interpolant automaton has 6 states. [2018-06-25 10:14:00,073 INFO ]: Start isEmpty. Operand 103 states and 171 transitions. [2018-06-25 10:14:00,074 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-25 10:14:00,074 INFO ]: Found error trace [2018-06-25 10:14:00,074 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:00,075 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:00,075 INFO ]: Analyzing trace with hash -804226993, now seen corresponding path program 1 times [2018-06-25 10:14:00,075 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:00,075 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:00,076 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:00,076 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:00,076 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:00,083 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:00,127 INFO ]: Checked inductivity of 5 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-25 10:14:00,127 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:14:00,127 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 10:14:00,128 INFO ]: Interpolant automaton has 3 states [2018-06-25 10:14:00,128 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 10:14:00,128 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 10:14:00,128 INFO ]: Start difference. First operand 103 states and 171 transitions. Second operand 3 states. [2018-06-25 10:14:00,140 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:00,140 INFO ]: Finished difference Result 42 states and 58 transitions. [2018-06-25 10:14:00,141 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 10:14:00,141 INFO ]: Start accepts. Automaton has 3 states. Word has length 20 [2018-06-25 10:14:00,141 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:00,141 INFO ]: With dead ends: 42 [2018-06-25 10:14:00,141 INFO ]: Without dead ends: 34 [2018-06-25 10:14:00,141 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 10:14:00,141 INFO ]: Start minimizeSevpa. Operand 34 states. [2018-06-25 10:14:00,144 INFO ]: Finished minimizeSevpa. Reduced states from 34 to 31. [2018-06-25 10:14:00,144 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-25 10:14:00,145 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2018-06-25 10:14:00,145 INFO ]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 20 [2018-06-25 10:14:00,145 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:00,145 INFO ]: Abstraction has 31 states and 41 transitions. [2018-06-25 10:14:00,145 INFO ]: Interpolant automaton has 3 states. [2018-06-25 10:14:00,145 INFO ]: Start isEmpty. Operand 31 states and 41 transitions. [2018-06-25 10:14:00,146 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-25 10:14:00,146 INFO ]: Found error trace [2018-06-25 10:14:00,146 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:00,146 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:00,146 INFO ]: Analyzing trace with hash -2020068231, now seen corresponding path program 1 times [2018-06-25 10:14:00,146 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:00,146 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:00,147 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:00,147 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:00,147 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:00,164 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:00,272 INFO ]: Checked inductivity of 8 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-25 10:14:00,272 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:00,272 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-25 10:14:00,280 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:00,315 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:00,323 INFO ]: Computing forward predicates... [2018-06-25 10:14:00,392 INFO ]: Checked inductivity of 8 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-25 10:14:00,411 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:00,411 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 7 [2018-06-25 10:14:00,411 INFO ]: Interpolant automaton has 7 states [2018-06-25 10:14:00,412 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 10:14:00,412 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-25 10:14:00,412 INFO ]: Start difference. First operand 31 states and 41 transitions. Second operand 7 states. [2018-06-25 10:14:00,517 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:00,517 INFO ]: Finished difference Result 41 states and 55 transitions. [2018-06-25 10:14:00,517 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 10:14:00,517 INFO ]: Start accepts. Automaton has 7 states. Word has length 20 [2018-06-25 10:14:00,517 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:00,518 INFO ]: With dead ends: 41 [2018-06-25 10:14:00,518 INFO ]: Without dead ends: 41 [2018-06-25 10:14:00,518 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2018-06-25 10:14:00,518 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-25 10:14:00,521 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 37. [2018-06-25 10:14:00,521 INFO ]: Start removeUnreachable. Operand 37 states. [2018-06-25 10:14:00,522 INFO ]: Finished removeUnreachable. Reduced from 37 states to 37 states and 49 transitions. [2018-06-25 10:14:00,522 INFO ]: Start accepts. Automaton has 37 states and 49 transitions. Word has length 20 [2018-06-25 10:14:00,522 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:00,522 INFO ]: Abstraction has 37 states and 49 transitions. [2018-06-25 10:14:00,522 INFO ]: Interpolant automaton has 7 states. [2018-06-25 10:14:00,522 INFO ]: Start isEmpty. Operand 37 states and 49 transitions. [2018-06-25 10:14:00,523 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-25 10:14:00,523 INFO ]: Found error trace [2018-06-25 10:14:00,523 INFO ]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:00,523 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:00,523 INFO ]: Analyzing trace with hash 1489077182, now seen corresponding path program 2 times [2018-06-25 10:14:00,523 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:00,523 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:00,524 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:00,524 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:00,524 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:00,540 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:00,668 INFO ]: Checked inductivity of 23 backedges. 15 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-25 10:14:00,668 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:00,668 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) [2018-06-25 10:14:00,690 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:00,743 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 10:14:00,743 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:00,745 INFO ]: Computing forward predicates... [2018-06-25 10:14:00,765 INFO ]: Checked inductivity of 23 backedges. 15 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-25 10:14:00,798 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:00,798 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-25 10:14:00,823 INFO ]: Interpolant automaton has 7 states [2018-06-25 10:14:00,824 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 10:14:00,824 INFO ]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-06-25 10:14:00,824 INFO ]: Start difference. First operand 37 states and 49 transitions. Second operand 7 states. [2018-06-25 10:14:01,505 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:01,505 INFO ]: Finished difference Result 45 states and 65 transitions. [2018-06-25 10:14:01,505 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-25 10:14:01,505 INFO ]: Start accepts. Automaton has 7 states. Word has length 28 [2018-06-25 10:14:01,506 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:01,506 INFO ]: With dead ends: 45 [2018-06-25 10:14:01,506 INFO ]: Without dead ends: 43 [2018-06-25 10:14:01,506 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=111, Unknown=0, NotChecked=0, Total=156 [2018-06-25 10:14:01,506 INFO ]: Start minimizeSevpa. Operand 43 states. [2018-06-25 10:14:01,510 INFO ]: Finished minimizeSevpa. Reduced states from 43 to 40. [2018-06-25 10:14:01,510 INFO ]: Start removeUnreachable. Operand 40 states. [2018-06-25 10:14:01,510 INFO ]: Finished removeUnreachable. Reduced from 40 states to 40 states and 53 transitions. [2018-06-25 10:14:01,510 INFO ]: Start accepts. Automaton has 40 states and 53 transitions. Word has length 28 [2018-06-25 10:14:01,511 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:01,511 INFO ]: Abstraction has 40 states and 53 transitions. [2018-06-25 10:14:01,511 INFO ]: Interpolant automaton has 7 states. [2018-06-25 10:14:01,511 INFO ]: Start isEmpty. Operand 40 states and 53 transitions. [2018-06-25 10:14:01,511 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-25 10:14:01,511 INFO ]: Found error trace [2018-06-25 10:14:01,512 INFO ]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:01,512 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:01,512 INFO ]: Analyzing trace with hash 978660881, now seen corresponding path program 3 times [2018-06-25 10:14:01,512 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:01,512 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:01,513 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:01,513 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:01,513 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:01,530 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:01,684 INFO ]: Checked inductivity of 27 backedges. 11 proven. 5 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-25 10:14:01,684 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:01,684 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 10:14:01,699 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:01,742 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 10:14:01,742 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:01,744 INFO ]: Computing forward predicates... [2018-06-25 10:14:01,882 INFO ]: Checked inductivity of 27 backedges. 14 proven. 6 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-25 10:14:01,901 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:01,901 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 14 [2018-06-25 10:14:01,901 INFO ]: Interpolant automaton has 14 states [2018-06-25 10:14:01,902 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-25 10:14:01,902 INFO ]: CoverageRelationStatistics Valid=32, Invalid=150, Unknown=0, NotChecked=0, Total=182 [2018-06-25 10:14:01,902 INFO ]: Start difference. First operand 40 states and 53 transitions. Second operand 14 states. [2018-06-25 10:14:02,478 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:02,479 INFO ]: Finished difference Result 86 states and 130 transitions. [2018-06-25 10:14:02,481 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-25 10:14:02,481 INFO ]: Start accepts. Automaton has 14 states. Word has length 29 [2018-06-25 10:14:02,481 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:02,482 INFO ]: With dead ends: 86 [2018-06-25 10:14:02,482 INFO ]: Without dead ends: 84 [2018-06-25 10:14:02,483 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=207, Invalid=849, Unknown=0, NotChecked=0, Total=1056 [2018-06-25 10:14:02,483 INFO ]: Start minimizeSevpa. Operand 84 states. [2018-06-25 10:14:02,488 INFO ]: Finished minimizeSevpa. Reduced states from 84 to 63. [2018-06-25 10:14:02,488 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-25 10:14:02,488 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 89 transitions. [2018-06-25 10:14:02,489 INFO ]: Start accepts. Automaton has 63 states and 89 transitions. Word has length 29 [2018-06-25 10:14:02,489 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:02,489 INFO ]: Abstraction has 63 states and 89 transitions. [2018-06-25 10:14:02,489 INFO ]: Interpolant automaton has 14 states. [2018-06-25 10:14:02,489 INFO ]: Start isEmpty. Operand 63 states and 89 transitions. [2018-06-25 10:14:02,490 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-25 10:14:02,490 INFO ]: Found error trace [2018-06-25 10:14:02,490 INFO ]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:02,490 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:02,490 INFO ]: Analyzing trace with hash 271824538, now seen corresponding path program 4 times [2018-06-25 10:14:02,490 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:02,490 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:02,491 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:02,491 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:02,491 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:02,527 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:02,628 INFO ]: Checked inductivity of 32 backedges. 13 proven. 5 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-06-25 10:14:02,629 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:02,629 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-25 10:14:02,635 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 10:14:02,659 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 10:14:02,659 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:02,662 INFO ]: Computing forward predicates... [2018-06-25 10:14:02,825 INFO ]: Checked inductivity of 32 backedges. 13 proven. 5 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-06-25 10:14:02,854 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:02,854 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-06-25 10:14:02,854 INFO ]: Interpolant automaton has 10 states [2018-06-25 10:14:02,854 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 10:14:02,855 INFO ]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-06-25 10:14:02,855 INFO ]: Start difference. First operand 63 states and 89 transitions. Second operand 10 states. [2018-06-25 10:14:03,049 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:03,049 INFO ]: Finished difference Result 87 states and 131 transitions. [2018-06-25 10:14:03,051 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 10:14:03,051 INFO ]: Start accepts. Automaton has 10 states. Word has length 30 [2018-06-25 10:14:03,051 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:03,052 INFO ]: With dead ends: 87 [2018-06-25 10:14:03,053 INFO ]: Without dead ends: 87 [2018-06-25 10:14:03,053 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2018-06-25 10:14:03,053 INFO ]: Start minimizeSevpa. Operand 87 states. [2018-06-25 10:14:03,065 INFO ]: Finished minimizeSevpa. Reduced states from 87 to 81. [2018-06-25 10:14:03,065 INFO ]: Start removeUnreachable. Operand 81 states. [2018-06-25 10:14:03,066 INFO ]: Finished removeUnreachable. Reduced from 81 states to 81 states and 119 transitions. [2018-06-25 10:14:03,067 INFO ]: Start accepts. Automaton has 81 states and 119 transitions. Word has length 30 [2018-06-25 10:14:03,067 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:03,067 INFO ]: Abstraction has 81 states and 119 transitions. [2018-06-25 10:14:03,067 INFO ]: Interpolant automaton has 10 states. [2018-06-25 10:14:03,067 INFO ]: Start isEmpty. Operand 81 states and 119 transitions. [2018-06-25 10:14:03,075 INFO ]: Finished isEmpty. Found accepting run of length 49 [2018-06-25 10:14:03,075 INFO ]: Found error trace [2018-06-25 10:14:03,075 INFO ]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:03,075 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:03,075 INFO ]: Analyzing trace with hash -822787686, now seen corresponding path program 5 times [2018-06-25 10:14:03,075 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:03,075 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:03,076 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:03,076 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:03,076 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:03,127 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:03,393 INFO ]: Checked inductivity of 107 backedges. 49 proven. 19 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-25 10:14:03,393 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:03,393 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-25 10:14:03,400 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 10:14:03,479 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 10:14:03,479 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:03,482 INFO ]: Computing forward predicates... [2018-06-25 10:14:03,972 INFO ]: Checked inductivity of 107 backedges. 69 proven. 11 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-06-25 10:14:03,991 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:03,991 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 14 [2018-06-25 10:14:03,992 INFO ]: Interpolant automaton has 14 states [2018-06-25 10:14:03,992 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-25 10:14:03,992 INFO ]: CoverageRelationStatistics Valid=30, Invalid=152, Unknown=0, NotChecked=0, Total=182 [2018-06-25 10:14:03,992 INFO ]: Start difference. First operand 81 states and 119 transitions. Second operand 14 states. [2018-06-25 10:14:04,552 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:04,552 INFO ]: Finished difference Result 92 states and 150 transitions. [2018-06-25 10:14:04,556 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-25 10:14:04,556 INFO ]: Start accepts. Automaton has 14 states. Word has length 48 [2018-06-25 10:14:04,556 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:04,558 INFO ]: With dead ends: 92 [2018-06-25 10:14:04,558 INFO ]: Without dead ends: 92 [2018-06-25 10:14:04,558 INFO ]: 0 DeclaredPredicates, 86 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 220 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=254, Invalid=936, Unknown=0, NotChecked=0, Total=1190 [2018-06-25 10:14:04,558 INFO ]: Start minimizeSevpa. Operand 92 states. [2018-06-25 10:14:04,564 INFO ]: Finished minimizeSevpa. Reduced states from 92 to 84. [2018-06-25 10:14:04,564 INFO ]: Start removeUnreachable. Operand 84 states. [2018-06-25 10:14:04,565 INFO ]: Finished removeUnreachable. Reduced from 84 states to 84 states and 128 transitions. [2018-06-25 10:14:04,565 INFO ]: Start accepts. Automaton has 84 states and 128 transitions. Word has length 48 [2018-06-25 10:14:04,566 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:04,566 INFO ]: Abstraction has 84 states and 128 transitions. [2018-06-25 10:14:04,566 INFO ]: Interpolant automaton has 14 states. [2018-06-25 10:14:04,566 INFO ]: Start isEmpty. Operand 84 states and 128 transitions. [2018-06-25 10:14:04,568 INFO ]: Finished isEmpty. Found accepting run of length 51 [2018-06-25 10:14:04,568 INFO ]: Found error trace [2018-06-25 10:14:04,568 INFO ]: trace histogram [7, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:04,568 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:04,568 INFO ]: Analyzing trace with hash -1221793072, now seen corresponding path program 6 times [2018-06-25 10:14:04,568 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:04,568 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:04,569 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:04,569 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:04,569 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:04,612 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:04,746 INFO ]: Checked inductivity of 128 backedges. 67 proven. 17 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2018-06-25 10:14:04,746 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:04,746 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:04,758 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 10:14:04,808 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-25 10:14:04,808 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:04,813 INFO ]: Computing forward predicates... [2018-06-25 10:14:05,076 INFO ]: Checked inductivity of 128 backedges. 59 proven. 43 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-06-25 10:14:05,105 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:05,105 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 15] total 22 [2018-06-25 10:14:05,106 INFO ]: Interpolant automaton has 22 states [2018-06-25 10:14:05,106 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-25 10:14:05,106 INFO ]: CoverageRelationStatistics Valid=49, Invalid=413, Unknown=0, NotChecked=0, Total=462 [2018-06-25 10:14:05,106 INFO ]: Start difference. First operand 84 states and 128 transitions. Second operand 22 states. [2018-06-25 10:14:06,451 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:06,451 INFO ]: Finished difference Result 105 states and 173 transitions. [2018-06-25 10:14:06,451 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-06-25 10:14:06,451 INFO ]: Start accepts. Automaton has 22 states. Word has length 50 [2018-06-25 10:14:06,452 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:06,453 INFO ]: With dead ends: 105 [2018-06-25 10:14:06,453 INFO ]: Without dead ends: 105 [2018-06-25 10:14:06,454 INFO ]: 0 DeclaredPredicates, 109 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 770 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=437, Invalid=2755, Unknown=0, NotChecked=0, Total=3192 [2018-06-25 10:14:06,454 INFO ]: Start minimizeSevpa. Operand 105 states. [2018-06-25 10:14:06,461 INFO ]: Finished minimizeSevpa. Reduced states from 105 to 83. [2018-06-25 10:14:06,461 INFO ]: Start removeUnreachable. Operand 83 states. [2018-06-25 10:14:06,462 INFO ]: Finished removeUnreachable. Reduced from 83 states to 83 states and 117 transitions. [2018-06-25 10:14:06,462 INFO ]: Start accepts. Automaton has 83 states and 117 transitions. Word has length 50 [2018-06-25 10:14:06,462 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:06,462 INFO ]: Abstraction has 83 states and 117 transitions. [2018-06-25 10:14:06,462 INFO ]: Interpolant automaton has 22 states. [2018-06-25 10:14:06,462 INFO ]: Start isEmpty. Operand 83 states and 117 transitions. [2018-06-25 10:14:06,463 INFO ]: Finished isEmpty. Found accepting run of length 51 [2018-06-25 10:14:06,463 INFO ]: Found error trace [2018-06-25 10:14:06,463 INFO ]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:06,464 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:06,464 INFO ]: Analyzing trace with hash -2031526955, now seen corresponding path program 1 times [2018-06-25 10:14:06,464 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:06,464 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:06,464 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:06,464 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:06,464 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:06,477 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:06,515 INFO ]: Checked inductivity of 108 backedges. 53 proven. 0 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-25 10:14:06,516 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 10:14:06,516 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 10:14:06,516 INFO ]: Interpolant automaton has 4 states [2018-06-25 10:14:06,516 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 10:14:06,516 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 10:14:06,516 INFO ]: Start difference. First operand 83 states and 117 transitions. Second operand 4 states. [2018-06-25 10:14:06,538 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:06,538 INFO ]: Finished difference Result 89 states and 123 transitions. [2018-06-25 10:14:06,538 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 10:14:06,538 INFO ]: Start accepts. Automaton has 4 states. Word has length 50 [2018-06-25 10:14:06,538 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:06,539 INFO ]: With dead ends: 89 [2018-06-25 10:14:06,539 INFO ]: Without dead ends: 79 [2018-06-25 10:14:06,539 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 10:14:06,540 INFO ]: Start minimizeSevpa. Operand 79 states. [2018-06-25 10:14:06,542 INFO ]: Finished minimizeSevpa. Reduced states from 79 to 79. [2018-06-25 10:14:06,542 INFO ]: Start removeUnreachable. Operand 79 states. [2018-06-25 10:14:06,543 INFO ]: Finished removeUnreachable. Reduced from 79 states to 79 states and 105 transitions. [2018-06-25 10:14:06,543 INFO ]: Start accepts. Automaton has 79 states and 105 transitions. Word has length 50 [2018-06-25 10:14:06,544 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:06,544 INFO ]: Abstraction has 79 states and 105 transitions. [2018-06-25 10:14:06,544 INFO ]: Interpolant automaton has 4 states. [2018-06-25 10:14:06,544 INFO ]: Start isEmpty. Operand 79 states and 105 transitions. [2018-06-25 10:14:06,545 INFO ]: Finished isEmpty. Found accepting run of length 52 [2018-06-25 10:14:06,545 INFO ]: Found error trace [2018-06-25 10:14:06,545 INFO ]: trace histogram [8, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:06,545 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:06,545 INFO ]: Analyzing trace with hash 330525367, now seen corresponding path program 7 times [2018-06-25 10:14:06,545 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:06,545 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:06,546 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:06,546 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:06,546 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:06,562 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:06,679 INFO ]: Checked inductivity of 140 backedges. 39 proven. 24 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2018-06-25 10:14:06,679 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:06,679 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-25 10:14:06,685 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:06,737 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:06,741 INFO ]: Computing forward predicates... [2018-06-25 10:14:06,859 INFO ]: Checked inductivity of 140 backedges. 45 proven. 18 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2018-06-25 10:14:06,878 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:06,878 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 14 [2018-06-25 10:14:06,878 INFO ]: Interpolant automaton has 14 states [2018-06-25 10:14:06,878 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-25 10:14:06,879 INFO ]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2018-06-25 10:14:06,879 INFO ]: Start difference. First operand 79 states and 105 transitions. Second operand 14 states. [2018-06-25 10:14:07,149 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:07,149 INFO ]: Finished difference Result 94 states and 138 transitions. [2018-06-25 10:14:07,150 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-25 10:14:07,150 INFO ]: Start accepts. Automaton has 14 states. Word has length 51 [2018-06-25 10:14:07,150 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:07,151 INFO ]: With dead ends: 94 [2018-06-25 10:14:07,151 INFO ]: Without dead ends: 94 [2018-06-25 10:14:07,151 INFO ]: 0 DeclaredPredicates, 71 GetRequests, 47 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=139, Invalid=367, Unknown=0, NotChecked=0, Total=506 [2018-06-25 10:14:07,151 INFO ]: Start minimizeSevpa. Operand 94 states. [2018-06-25 10:14:07,156 INFO ]: Finished minimizeSevpa. Reduced states from 94 to 82. [2018-06-25 10:14:07,156 INFO ]: Start removeUnreachable. Operand 82 states. [2018-06-25 10:14:07,157 INFO ]: Finished removeUnreachable. Reduced from 82 states to 82 states and 108 transitions. [2018-06-25 10:14:07,157 INFO ]: Start accepts. Automaton has 82 states and 108 transitions. Word has length 51 [2018-06-25 10:14:07,157 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:07,157 INFO ]: Abstraction has 82 states and 108 transitions. [2018-06-25 10:14:07,157 INFO ]: Interpolant automaton has 14 states. [2018-06-25 10:14:07,157 INFO ]: Start isEmpty. Operand 82 states and 108 transitions. [2018-06-25 10:14:07,158 INFO ]: Finished isEmpty. Found accepting run of length 53 [2018-06-25 10:14:07,158 INFO ]: Found error trace [2018-06-25 10:14:07,158 INFO ]: trace histogram [9, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:07,159 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:07,159 INFO ]: Analyzing trace with hash 1654460084, now seen corresponding path program 8 times [2018-06-25 10:14:07,159 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:07,159 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:07,159 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:07,159 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:07,159 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:07,175 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:07,559 INFO ]: Checked inductivity of 153 backedges. 49 proven. 27 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2018-06-25 10:14:07,559 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:07,559 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-25 10:14:07,565 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 10:14:07,612 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 10:14:07,612 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:07,616 INFO ]: Computing forward predicates... [2018-06-25 10:14:07,753 INFO ]: Checked inductivity of 153 backedges. 55 proven. 21 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2018-06-25 10:14:07,782 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:07,782 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 16 [2018-06-25 10:14:07,782 INFO ]: Interpolant automaton has 16 states [2018-06-25 10:14:07,783 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-25 10:14:07,783 INFO ]: CoverageRelationStatistics Valid=47, Invalid=193, Unknown=0, NotChecked=0, Total=240 [2018-06-25 10:14:07,783 INFO ]: Start difference. First operand 82 states and 108 transitions. Second operand 16 states. [2018-06-25 10:14:08,087 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:08,088 INFO ]: Finished difference Result 97 states and 141 transitions. [2018-06-25 10:14:08,088 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-25 10:14:08,088 INFO ]: Start accepts. Automaton has 16 states. Word has length 52 [2018-06-25 10:14:08,088 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:08,089 INFO ]: With dead ends: 97 [2018-06-25 10:14:08,089 INFO ]: Without dead ends: 97 [2018-06-25 10:14:08,089 INFO ]: 0 DeclaredPredicates, 74 GetRequests, 48 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=172, Invalid=478, Unknown=0, NotChecked=0, Total=650 [2018-06-25 10:14:08,089 INFO ]: Start minimizeSevpa. Operand 97 states. [2018-06-25 10:14:08,094 INFO ]: Finished minimizeSevpa. Reduced states from 97 to 85. [2018-06-25 10:14:08,094 INFO ]: Start removeUnreachable. Operand 85 states. [2018-06-25 10:14:08,096 INFO ]: Finished removeUnreachable. Reduced from 85 states to 85 states and 111 transitions. [2018-06-25 10:14:08,096 INFO ]: Start accepts. Automaton has 85 states and 111 transitions. Word has length 52 [2018-06-25 10:14:08,096 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:08,096 INFO ]: Abstraction has 85 states and 111 transitions. [2018-06-25 10:14:08,096 INFO ]: Interpolant automaton has 16 states. [2018-06-25 10:14:08,096 INFO ]: Start isEmpty. Operand 85 states and 111 transitions. [2018-06-25 10:14:08,097 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-25 10:14:08,097 INFO ]: Found error trace [2018-06-25 10:14:08,098 INFO ]: trace histogram [10, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:08,098 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:08,098 INFO ]: Analyzing trace with hash -253236649, now seen corresponding path program 9 times [2018-06-25 10:14:08,098 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:08,098 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:08,098 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:08,098 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:08,098 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:08,116 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:08,402 INFO ]: Checked inductivity of 167 backedges. 58 proven. 22 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2018-06-25 10:14:08,402 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:08,402 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-25 10:14:08,410 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 10:14:08,448 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-25 10:14:08,448 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:08,452 INFO ]: Computing forward predicates... [2018-06-25 10:14:09,077 INFO ]: Checked inductivity of 167 backedges. 71 proven. 39 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2018-06-25 10:14:09,097 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:09,097 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 16] total 25 [2018-06-25 10:14:09,098 INFO ]: Interpolant automaton has 25 states [2018-06-25 10:14:09,098 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-25 10:14:09,098 INFO ]: CoverageRelationStatistics Valid=66, Invalid=534, Unknown=0, NotChecked=0, Total=600 [2018-06-25 10:14:09,098 INFO ]: Start difference. First operand 85 states and 111 transitions. Second operand 25 states. [2018-06-25 10:14:10,089 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:10,089 INFO ]: Finished difference Result 169 states and 225 transitions. [2018-06-25 10:14:10,090 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-06-25 10:14:10,090 INFO ]: Start accepts. Automaton has 25 states. Word has length 53 [2018-06-25 10:14:10,091 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:10,093 INFO ]: With dead ends: 169 [2018-06-25 10:14:10,093 INFO ]: Without dead ends: 167 [2018-06-25 10:14:10,093 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 368 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=331, Invalid=1649, Unknown=0, NotChecked=0, Total=1980 [2018-06-25 10:14:10,094 INFO ]: Start minimizeSevpa. Operand 167 states. [2018-06-25 10:14:10,100 INFO ]: Finished minimizeSevpa. Reduced states from 167 to 132. [2018-06-25 10:14:10,100 INFO ]: Start removeUnreachable. Operand 132 states. [2018-06-25 10:14:10,103 INFO ]: Finished removeUnreachable. Reduced from 132 states to 132 states and 178 transitions. [2018-06-25 10:14:10,103 INFO ]: Start accepts. Automaton has 132 states and 178 transitions. Word has length 53 [2018-06-25 10:14:10,104 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:10,104 INFO ]: Abstraction has 132 states and 178 transitions. [2018-06-25 10:14:10,104 INFO ]: Interpolant automaton has 25 states. [2018-06-25 10:14:10,104 INFO ]: Start isEmpty. Operand 132 states and 178 transitions. [2018-06-25 10:14:10,108 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-25 10:14:10,108 INFO ]: Found error trace [2018-06-25 10:14:10,108 INFO ]: trace histogram [14, 6, 6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:10,109 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:10,109 INFO ]: Analyzing trace with hash -757170574, now seen corresponding path program 10 times [2018-06-25 10:14:10,109 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:10,109 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:10,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:10,109 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:10,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:10,130 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:10,398 INFO ]: Checked inductivity of 285 backedges. 123 proven. 78 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-06-25 10:14:10,398 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:10,398 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:10,409 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 10:14:10,455 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 10:14:10,455 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:10,458 INFO ]: Computing forward predicates... [2018-06-25 10:14:10,559 INFO ]: Checked inductivity of 285 backedges. 162 proven. 13 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2018-06-25 10:14:10,579 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:10,579 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 11] total 20 [2018-06-25 10:14:10,579 INFO ]: Interpolant automaton has 20 states [2018-06-25 10:14:10,579 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-25 10:14:10,580 INFO ]: CoverageRelationStatistics Valid=44, Invalid=336, Unknown=0, NotChecked=0, Total=380 [2018-06-25 10:14:10,580 INFO ]: Start difference. First operand 132 states and 178 transitions. Second operand 20 states. [2018-06-25 10:14:11,036 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:11,036 INFO ]: Finished difference Result 177 states and 253 transitions. [2018-06-25 10:14:11,037 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-25 10:14:11,037 INFO ]: Start accepts. Automaton has 20 states. Word has length 65 [2018-06-25 10:14:11,037 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:11,039 INFO ]: With dead ends: 177 [2018-06-25 10:14:11,039 INFO ]: Without dead ends: 173 [2018-06-25 10:14:11,040 INFO ]: 0 DeclaredPredicates, 99 GetRequests, 60 SyntacticMatches, 1 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 291 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=205, Invalid=1355, Unknown=0, NotChecked=0, Total=1560 [2018-06-25 10:14:11,040 INFO ]: Start minimizeSevpa. Operand 173 states. [2018-06-25 10:14:11,052 INFO ]: Finished minimizeSevpa. Reduced states from 173 to 163. [2018-06-25 10:14:11,052 INFO ]: Start removeUnreachable. Operand 163 states. [2018-06-25 10:14:11,055 INFO ]: Finished removeUnreachable. Reduced from 163 states to 163 states and 228 transitions. [2018-06-25 10:14:11,055 INFO ]: Start accepts. Automaton has 163 states and 228 transitions. Word has length 65 [2018-06-25 10:14:11,055 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:11,055 INFO ]: Abstraction has 163 states and 228 transitions. [2018-06-25 10:14:11,055 INFO ]: Interpolant automaton has 20 states. [2018-06-25 10:14:11,055 INFO ]: Start isEmpty. Operand 163 states and 228 transitions. [2018-06-25 10:14:11,058 INFO ]: Finished isEmpty. Found accepting run of length 98 [2018-06-25 10:14:11,058 INFO ]: Found error trace [2018-06-25 10:14:11,059 INFO ]: trace histogram [22, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:11,059 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:11,059 INFO ]: Analyzing trace with hash 441138391, now seen corresponding path program 11 times [2018-06-25 10:14:11,059 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:11,059 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:11,059 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:11,059 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:11,059 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:11,090 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:11,349 INFO ]: Checked inductivity of 701 backedges. 288 proven. 109 refuted. 0 times theorem prover too weak. 304 trivial. 0 not checked. [2018-06-25 10:14:11,349 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:11,349 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:11,355 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 10:14:11,420 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-25 10:14:11,420 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:11,425 INFO ]: Computing forward predicates... [2018-06-25 10:14:11,618 INFO ]: Checked inductivity of 701 backedges. 424 proven. 42 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2018-06-25 10:14:11,651 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:11,651 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 23 [2018-06-25 10:14:11,651 INFO ]: Interpolant automaton has 23 states [2018-06-25 10:14:11,651 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-25 10:14:11,651 INFO ]: CoverageRelationStatistics Valid=52, Invalid=454, Unknown=0, NotChecked=0, Total=506 [2018-06-25 10:14:11,652 INFO ]: Start difference. First operand 163 states and 228 transitions. Second operand 23 states. [2018-06-25 10:14:16,569 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:16,569 INFO ]: Finished difference Result 991 states and 2620 transitions. [2018-06-25 10:14:16,569 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-06-25 10:14:16,569 INFO ]: Start accepts. Automaton has 23 states. Word has length 97 [2018-06-25 10:14:16,569 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:16,590 INFO ]: With dead ends: 991 [2018-06-25 10:14:16,590 INFO ]: Without dead ends: 991 [2018-06-25 10:14:16,593 INFO ]: 0 DeclaredPredicates, 215 GetRequests, 103 SyntacticMatches, 3 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3813 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=1722, Invalid=10488, Unknown=0, NotChecked=0, Total=12210 [2018-06-25 10:14:16,594 INFO ]: Start minimizeSevpa. Operand 991 states. [2018-06-25 10:14:16,695 INFO ]: Finished minimizeSevpa. Reduced states from 991 to 466. [2018-06-25 10:14:16,695 INFO ]: Start removeUnreachable. Operand 466 states. [2018-06-25 10:14:16,705 INFO ]: Finished removeUnreachable. Reduced from 466 states to 466 states and 771 transitions. [2018-06-25 10:14:16,705 INFO ]: Start accepts. Automaton has 466 states and 771 transitions. Word has length 97 [2018-06-25 10:14:16,705 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:16,705 INFO ]: Abstraction has 466 states and 771 transitions. [2018-06-25 10:14:16,705 INFO ]: Interpolant automaton has 23 states. [2018-06-25 10:14:16,706 INFO ]: Start isEmpty. Operand 466 states and 771 transitions. [2018-06-25 10:14:16,713 INFO ]: Finished isEmpty. Found accepting run of length 102 [2018-06-25 10:14:16,713 INFO ]: Found error trace [2018-06-25 10:14:16,713 INFO ]: trace histogram [26, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:16,713 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:16,713 INFO ]: Analyzing trace with hash 1635233987, now seen corresponding path program 12 times [2018-06-25 10:14:16,713 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:16,713 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:16,714 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:16,714 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:16,714 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:16,751 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:17,428 INFO ]: Checked inductivity of 831 backedges. 343 proven. 121 refuted. 0 times theorem prover too weak. 367 trivial. 0 not checked. [2018-06-25 10:14:17,428 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:17,428 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:17,436 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 10:14:17,538 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2018-06-25 10:14:17,538 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:17,542 INFO ]: Computing forward predicates... [2018-06-25 10:14:17,864 INFO ]: Checked inductivity of 831 backedges. 425 proven. 47 refuted. 0 times theorem prover too weak. 359 trivial. 0 not checked. [2018-06-25 10:14:17,884 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:17,885 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 17] total 30 [2018-06-25 10:14:17,885 INFO ]: Interpolant automaton has 30 states [2018-06-25 10:14:17,885 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-25 10:14:17,885 INFO ]: CoverageRelationStatistics Valid=69, Invalid=801, Unknown=0, NotChecked=0, Total=870 [2018-06-25 10:14:17,885 INFO ]: Start difference. First operand 466 states and 771 transitions. Second operand 30 states. [2018-06-25 10:14:18,805 WARN ]: Spent 277.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 17 [2018-06-25 10:14:20,557 WARN ]: Spent 267.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 18 [2018-06-25 10:14:22,831 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 31 [2018-06-25 10:14:23,637 WARN ]: Spent 129.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 28 [2018-06-25 10:14:25,152 WARN ]: Spent 264.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 21 [2018-06-25 10:14:25,654 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 26 [2018-06-25 10:14:25,895 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:25,895 INFO ]: Finished difference Result 1264 states and 3535 transitions. [2018-06-25 10:14:25,895 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 132 states. [2018-06-25 10:14:25,895 INFO ]: Start accepts. Automaton has 30 states. Word has length 101 [2018-06-25 10:14:25,895 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:25,952 INFO ]: With dead ends: 1264 [2018-06-25 10:14:25,952 INFO ]: Without dead ends: 1264 [2018-06-25 10:14:25,959 INFO ]: 0 DeclaredPredicates, 265 GetRequests, 110 SyntacticMatches, 2 SemanticMatches, 153 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7925 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=2755, Invalid=21115, Unknown=0, NotChecked=0, Total=23870 [2018-06-25 10:14:25,961 INFO ]: Start minimizeSevpa. Operand 1264 states. [2018-06-25 10:14:26,140 INFO ]: Finished minimizeSevpa. Reduced states from 1264 to 645. [2018-06-25 10:14:26,140 INFO ]: Start removeUnreachable. Operand 645 states. [2018-06-25 10:14:26,148 INFO ]: Finished removeUnreachable. Reduced from 645 states to 645 states and 1155 transitions. [2018-06-25 10:14:26,149 INFO ]: Start accepts. Automaton has 645 states and 1155 transitions. Word has length 101 [2018-06-25 10:14:26,149 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:26,149 INFO ]: Abstraction has 645 states and 1155 transitions. [2018-06-25 10:14:26,149 INFO ]: Interpolant automaton has 30 states. [2018-06-25 10:14:26,149 INFO ]: Start isEmpty. Operand 645 states and 1155 transitions. [2018-06-25 10:14:26,157 INFO ]: Finished isEmpty. Found accepting run of length 105 [2018-06-25 10:14:26,157 INFO ]: Found error trace [2018-06-25 10:14:26,158 INFO ]: trace histogram [29, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:26,158 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:26,158 INFO ]: Analyzing trace with hash -1592625510, now seen corresponding path program 13 times [2018-06-25 10:14:26,158 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:26,158 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:26,159 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:26,159 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:26,159 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:26,192 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:26,620 INFO ]: Checked inductivity of 939 backedges. 359 proven. 166 refuted. 0 times theorem prover too weak. 414 trivial. 0 not checked. [2018-06-25 10:14:26,620 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:26,620 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 10:14:26,635 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:26,714 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:26,719 INFO ]: Computing forward predicates... [2018-06-25 10:14:27,072 INFO ]: Checked inductivity of 939 backedges. 518 proven. 66 refuted. 0 times theorem prover too weak. 355 trivial. 0 not checked. [2018-06-25 10:14:27,091 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:27,091 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 27 [2018-06-25 10:14:27,092 INFO ]: Interpolant automaton has 27 states [2018-06-25 10:14:27,092 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-25 10:14:27,092 INFO ]: CoverageRelationStatistics Valid=64, Invalid=638, Unknown=0, NotChecked=0, Total=702 [2018-06-25 10:14:27,092 INFO ]: Start difference. First operand 645 states and 1155 transitions. Second operand 27 states. [2018-06-25 10:14:31,162 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:31,162 INFO ]: Finished difference Result 1012 states and 2362 transitions. [2018-06-25 10:14:31,163 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-06-25 10:14:31,163 INFO ]: Start accepts. Automaton has 27 states. Word has length 104 [2018-06-25 10:14:31,163 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:31,189 INFO ]: With dead ends: 1012 [2018-06-25 10:14:31,189 INFO ]: Without dead ends: 1012 [2018-06-25 10:14:31,192 INFO ]: 0 DeclaredPredicates, 203 GetRequests, 99 SyntacticMatches, 5 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2810 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=1485, Invalid=8615, Unknown=0, NotChecked=0, Total=10100 [2018-06-25 10:14:31,194 INFO ]: Start minimizeSevpa. Operand 1012 states. [2018-06-25 10:14:31,257 INFO ]: Finished minimizeSevpa. Reduced states from 1012 to 809. [2018-06-25 10:14:31,257 INFO ]: Start removeUnreachable. Operand 809 states. [2018-06-25 10:14:31,269 INFO ]: Finished removeUnreachable. Reduced from 809 states to 809 states and 1634 transitions. [2018-06-25 10:14:31,269 INFO ]: Start accepts. Automaton has 809 states and 1634 transitions. Word has length 104 [2018-06-25 10:14:31,269 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:31,269 INFO ]: Abstraction has 809 states and 1634 transitions. [2018-06-25 10:14:31,269 INFO ]: Interpolant automaton has 27 states. [2018-06-25 10:14:31,269 INFO ]: Start isEmpty. Operand 809 states and 1634 transitions. [2018-06-25 10:14:31,279 INFO ]: Finished isEmpty. Found accepting run of length 107 [2018-06-25 10:14:31,279 INFO ]: Found error trace [2018-06-25 10:14:31,280 INFO ]: trace histogram [31, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:31,280 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:31,280 INFO ]: Analyzing trace with hash 201066320, now seen corresponding path program 14 times [2018-06-25 10:14:31,280 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:31,280 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:31,280 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:31,280 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 10:14:31,280 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:31,313 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:31,790 INFO ]: Checked inductivity of 1016 backedges. 435 proven. 142 refuted. 0 times theorem prover too weak. 439 trivial. 0 not checked. [2018-06-25 10:14:31,790 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:31,790 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:31,796 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 10:14:31,880 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 10:14:31,880 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:31,884 INFO ]: Computing forward predicates... [2018-06-25 10:14:32,128 INFO ]: Checked inductivity of 1016 backedges. 423 proven. 91 refuted. 0 times theorem prover too weak. 502 trivial. 0 not checked. [2018-06-25 10:14:32,147 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:32,147 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 19] total 29 [2018-06-25 10:14:32,148 INFO ]: Interpolant automaton has 29 states [2018-06-25 10:14:32,148 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-25 10:14:32,148 INFO ]: CoverageRelationStatistics Valid=71, Invalid=741, Unknown=0, NotChecked=0, Total=812 [2018-06-25 10:14:32,148 INFO ]: Start difference. First operand 809 states and 1634 transitions. Second operand 29 states. [2018-06-25 10:14:35,761 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:35,761 INFO ]: Finished difference Result 1112 states and 2986 transitions. [2018-06-25 10:14:35,762 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2018-06-25 10:14:35,762 INFO ]: Start accepts. Automaton has 29 states. Word has length 106 [2018-06-25 10:14:35,762 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:35,791 INFO ]: With dead ends: 1112 [2018-06-25 10:14:35,791 INFO ]: Without dead ends: 1112 [2018-06-25 10:14:35,793 INFO ]: 0 DeclaredPredicates, 226 GetRequests, 102 SyntacticMatches, 5 SemanticMatches, 119 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4318 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=2166, Invalid=12354, Unknown=0, NotChecked=0, Total=14520 [2018-06-25 10:14:35,793 INFO ]: Start minimizeSevpa. Operand 1112 states. [2018-06-25 10:14:35,897 INFO ]: Finished minimizeSevpa. Reduced states from 1112 to 896. [2018-06-25 10:14:35,897 INFO ]: Start removeUnreachable. Operand 896 states. [2018-06-25 10:14:35,910 INFO ]: Finished removeUnreachable. Reduced from 896 states to 896 states and 1980 transitions. [2018-06-25 10:14:35,910 INFO ]: Start accepts. Automaton has 896 states and 1980 transitions. Word has length 106 [2018-06-25 10:14:35,910 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:35,910 INFO ]: Abstraction has 896 states and 1980 transitions. [2018-06-25 10:14:35,910 INFO ]: Interpolant automaton has 29 states. [2018-06-25 10:14:35,910 INFO ]: Start isEmpty. Operand 896 states and 1980 transitions. [2018-06-25 10:14:35,923 INFO ]: Finished isEmpty. Found accepting run of length 108 [2018-06-25 10:14:35,923 INFO ]: Found error trace [2018-06-25 10:14:35,923 INFO ]: trace histogram [32, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:35,923 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:35,923 INFO ]: Analyzing trace with hash -2143973577, now seen corresponding path program 15 times [2018-06-25 10:14:35,923 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:35,923 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:35,926 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:35,926 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:35,926 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:35,959 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:36,576 INFO ]: Checked inductivity of 1056 backedges. 223 proven. 156 refuted. 0 times theorem prover too weak. 677 trivial. 0 not checked. [2018-06-25 10:14:36,576 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:36,576 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:36,582 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 10:14:36,646 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-06-25 10:14:36,646 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:36,650 INFO ]: Computing forward predicates... [2018-06-25 10:14:36,982 INFO ]: Checked inductivity of 1056 backedges. 354 proven. 125 refuted. 0 times theorem prover too weak. 577 trivial. 0 not checked. [2018-06-25 10:14:37,001 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:37,001 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 32 [2018-06-25 10:14:37,002 INFO ]: Interpolant automaton has 32 states [2018-06-25 10:14:37,002 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-25 10:14:37,002 INFO ]: CoverageRelationStatistics Valid=91, Invalid=901, Unknown=0, NotChecked=0, Total=992 [2018-06-25 10:14:37,002 INFO ]: Start difference. First operand 896 states and 1980 transitions. Second operand 32 states. [2018-06-25 10:14:42,008 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:42,009 INFO ]: Finished difference Result 2203 states and 7881 transitions. [2018-06-25 10:14:42,010 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 102 states. [2018-06-25 10:14:42,010 INFO ]: Start accepts. Automaton has 32 states. Word has length 107 [2018-06-25 10:14:42,011 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:42,095 INFO ]: With dead ends: 2203 [2018-06-25 10:14:42,095 INFO ]: Without dead ends: 2201 [2018-06-25 10:14:42,097 INFO ]: 0 DeclaredPredicates, 238 GetRequests, 110 SyntacticMatches, 3 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4081 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=2357, Invalid=13645, Unknown=0, NotChecked=0, Total=16002 [2018-06-25 10:14:42,098 INFO ]: Start minimizeSevpa. Operand 2201 states. [2018-06-25 10:14:42,337 INFO ]: Finished minimizeSevpa. Reduced states from 2201 to 1571. [2018-06-25 10:14:42,337 INFO ]: Start removeUnreachable. Operand 1571 states. [2018-06-25 10:14:42,365 INFO ]: Finished removeUnreachable. Reduced from 1571 states to 1571 states and 3426 transitions. [2018-06-25 10:14:42,365 INFO ]: Start accepts. Automaton has 1571 states and 3426 transitions. Word has length 107 [2018-06-25 10:14:42,365 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:42,365 INFO ]: Abstraction has 1571 states and 3426 transitions. [2018-06-25 10:14:42,365 INFO ]: Interpolant automaton has 32 states. [2018-06-25 10:14:42,365 INFO ]: Start isEmpty. Operand 1571 states and 3426 transitions. [2018-06-25 10:14:42,386 INFO ]: Finished isEmpty. Found accepting run of length 109 [2018-06-25 10:14:42,386 INFO ]: Found error trace [2018-06-25 10:14:42,386 INFO ]: trace histogram [33, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:42,386 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:42,387 INFO ]: Analyzing trace with hash -2040563148, now seen corresponding path program 16 times [2018-06-25 10:14:42,387 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:42,387 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:42,387 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:42,387 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:42,387 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:42,422 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:43,008 INFO ]: Checked inductivity of 1097 backedges. 257 proven. 163 refuted. 0 times theorem prover too weak. 677 trivial. 0 not checked. [2018-06-25 10:14:43,009 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:43,009 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:43,016 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 10:14:43,125 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 10:14:43,125 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:43,132 INFO ]: Computing forward predicates... [2018-06-25 10:14:43,558 INFO ]: Checked inductivity of 1097 backedges. 247 proven. 92 refuted. 0 times theorem prover too weak. 758 trivial. 0 not checked. [2018-06-25 10:14:43,578 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:43,578 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18] total 27 [2018-06-25 10:14:43,578 INFO ]: Interpolant automaton has 27 states [2018-06-25 10:14:43,578 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-25 10:14:43,579 INFO ]: CoverageRelationStatistics Valid=91, Invalid=611, Unknown=0, NotChecked=0, Total=702 [2018-06-25 10:14:43,579 INFO ]: Start difference. First operand 1571 states and 3426 transitions. Second operand 27 states. [2018-06-25 10:14:45,623 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 10:14:45,624 INFO ]: Finished difference Result 1989 states and 5414 transitions. [2018-06-25 10:14:45,624 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-25 10:14:45,624 INFO ]: Start accepts. Automaton has 27 states. Word has length 108 [2018-06-25 10:14:45,624 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 10:14:45,677 INFO ]: With dead ends: 1989 [2018-06-25 10:14:45,677 INFO ]: Without dead ends: 1989 [2018-06-25 10:14:45,677 INFO ]: 0 DeclaredPredicates, 183 GetRequests, 101 SyntacticMatches, 7 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 910 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1262, Invalid=4590, Unknown=0, NotChecked=0, Total=5852 [2018-06-25 10:14:45,678 INFO ]: Start minimizeSevpa. Operand 1989 states. [2018-06-25 10:14:45,818 INFO ]: Finished minimizeSevpa. Reduced states from 1989 to 1603. [2018-06-25 10:14:45,818 INFO ]: Start removeUnreachable. Operand 1603 states. [2018-06-25 10:14:45,848 INFO ]: Finished removeUnreachable. Reduced from 1603 states to 1603 states and 3466 transitions. [2018-06-25 10:14:45,848 INFO ]: Start accepts. Automaton has 1603 states and 3466 transitions. Word has length 108 [2018-06-25 10:14:45,849 INFO ]: Finished accepts. word is rejected. [2018-06-25 10:14:45,849 INFO ]: Abstraction has 1603 states and 3466 transitions. [2018-06-25 10:14:45,849 INFO ]: Interpolant automaton has 27 states. [2018-06-25 10:14:45,849 INFO ]: Start isEmpty. Operand 1603 states and 3466 transitions. [2018-06-25 10:14:45,862 INFO ]: Finished isEmpty. Found accepting run of length 110 [2018-06-25 10:14:45,862 INFO ]: Found error trace [2018-06-25 10:14:45,862 INFO ]: trace histogram [34, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 10:14:45,862 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 10:14:45,862 INFO ]: Analyzing trace with hash 1165160151, now seen corresponding path program 17 times [2018-06-25 10:14:45,862 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 10:14:45,862 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 10:14:45,863 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:45,863 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 10:14:45,863 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 10:14:45,898 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:46,707 INFO ]: Checked inductivity of 1139 backedges. 291 proven. 171 refuted. 0 times theorem prover too weak. 677 trivial. 0 not checked. [2018-06-25 10:14:46,707 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 10:14:46,707 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 10:14:46,713 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 10:14:46,819 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-25 10:14:46,819 INFO ]: Conjunction of SSA is unsat [2018-06-25 10:14:46,825 INFO ]: Computing forward predicates... [2018-06-25 10:14:48,894 INFO ]: Checked inductivity of 1139 backedges. 276 proven. 173 refuted. 0 times theorem prover too weak. 690 trivial. 0 not checked. [2018-06-25 10:14:48,913 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 10:14:48,913 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 24] total 43 [2018-06-25 10:14:48,914 INFO ]: Interpolant automaton has 43 states [2018-06-25 10:14:48,914 INFO ]: Constructing interpolant automaton starting with 43 interpolants. [2018-06-25 10:14:48,914 INFO ]: CoverageRelationStatistics Valid=98, Invalid=1704, Unknown=4, NotChecked=0, Total=1806 [2018-06-25 10:14:48,914 INFO ]: Start difference. First operand 1603 states and 3466 transitions. Second operand 43 states. [2018-06-25 10:14:50,782 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 36 [2018-06-25 10:14:55,267 WARN ]: Spent 4.05 s on a formula simplification. DAG size of input: 41 DAG size of output: 39 [2018-06-25 10:14:56,045 WARN ]: Spent 314.00 ms on a formula simplification that was a NOOP. DAG size: 36 Received shutdown request... [2018-06-25 10:14:58,125 WARN ]: Removed 5 from assertion stack [2018-06-25 10:14:58,125 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 10:14:58,125 WARN ]: Verification canceled [2018-06-25 10:14:58,129 WARN ]: Timeout [2018-06-25 10:14:58,129 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 10:14:58 BoogieIcfgContainer [2018-06-25 10:14:58,129 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 10:14:58,130 INFO ]: Toolchain (without parser) took 61150.84 ms. Allocated memory was 308.8 MB in the beginning and 738.2 MB in the end (delta: 429.4 MB). Free memory was 264.2 MB in the beginning and 402.2 MB in the end (delta: -138.0 MB). Peak memory consumption was 291.4 MB. Max. memory is 3.6 GB. [2018-06-25 10:14:58,131 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 10:14:58,131 INFO ]: ChcToBoogie took 59.37 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 10:14:58,131 INFO ]: Boogie Preprocessor took 42.21 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 260.2 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-25 10:14:58,132 INFO ]: RCFGBuilder took 430.05 ms. Allocated memory is still 308.8 MB. Free memory was 260.2 MB in the beginning and 248.2 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. [2018-06-25 10:14:58,132 INFO ]: TraceAbstraction took 60608.48 ms. Allocated memory was 308.8 MB in the beginning and 738.2 MB in the end (delta: 429.4 MB). Free memory was 247.2 MB in the beginning and 402.2 MB in the end (delta: -154.9 MB). Peak memory consumption was 274.4 MB. Max. memory is 3.6 GB. [2018-06-25 10:14:58,135 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 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 59.37 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 42.21 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 260.2 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 430.05 ms. Allocated memory is still 308.8 MB. Free memory was 260.2 MB in the beginning and 248.2 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 60608.48 ms. Allocated memory was 308.8 MB in the beginning and 738.2 MB in the end (delta: 429.4 MB). Free memory was 247.2 MB in the beginning and 402.2 MB in the end (delta: -154.9 MB). Peak memory consumption was 274.4 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 constructing difference of abstraction (1603states) and interpolant automaton (currently 11 states, 43 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 49. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 28 locations, 1 error locations. TIMEOUT Result, 60.5s OverallTime, 24 OverallIterations, 34 TraceHistogramMax, 44.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 926 SDtfs, 2263 SDslu, 5948 SDs, 0 SdLazy, 18919 SolverSat, 2083 SolverUnsat, 1 SolverUnknown, 0 SolverNotchecked, 13.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2189 GetRequests, 1129 SyntacticMatches, 35 SemanticMatches, 1024 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26100 ImplicationChecksByTransitivity, 36.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=1603occurred in iteration=23, 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: 1.1s AutomataMinimizationTime, 23 MinimizatonAttempts, 2889 StatesRemovedByMinimization, 19 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 12.4s InterpolantComputationTime, 2442 NumberOfCodeBlocks, 2354 NumberOfCodeBlocksAsserted, 84 NumberOfCheckSat, 2401 ConstructedInterpolants, 9 QuantifiedInterpolants, 546572 SizeOfPredicates, 88 NumberOfNonLiveVariables, 7882 ConjunctsInSsa, 668 ConjunctsInUnsatCore, 41 InterpolantComputations, 7 PerfectInterpolantSequences, 13796/15817 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/rec__triangular.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_10-14-58-226.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/rec__triangular.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_10-14-58-226.csv Completed graceful shutdown