java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/eldarica-misc/LIA/reve/019b-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:29:09,189 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:29:09,192 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:29:09,204 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:29:09,205 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:29:09,205 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:29:09,209 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:29:09,211 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:29:09,213 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:29:09,213 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:29:09,215 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:29:09,215 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:29:09,216 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:29:09,217 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:29:09,217 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:29:09,220 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:29:09,221 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:29:09,232 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:29:09,233 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:29:09,234 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:29:09,239 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:29:09,241 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:29:09,241 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:29:09,242 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:29:09,242 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:29:09,243 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:29:09,244 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:29:09,244 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:29:09,245 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:29:09,245 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:29:09,248 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:29:09,249 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:29:09,249 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:29:09,250 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:29:09,250 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:29:09,251 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:29:09,273 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:29:09,274 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:29:09,274 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:29:09,274 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:29:09,276 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:29:09,276 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:29:09,276 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:29:09,276 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:29:09,276 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:29:09,276 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:29:09,277 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:29:09,277 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:29:09,277 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:29:09,278 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:29:09,278 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:29:09,278 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:29:09,278 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:29:09,280 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:29:09,280 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:29:09,318 INFO ]: Repository-Root is: /tmp [2018-06-22 01:29:09,335 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:29:09,342 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:29:09,344 INFO ]: Initializing SmtParser... [2018-06-22 01:29:09,344 INFO ]: SmtParser initialized [2018-06-22 01:29:09,345 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/019b-horn.smt2 [2018-06-22 01:29:09,346 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 01:29:09,439 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/019b-horn.smt2 unknown [2018-06-22 01:29:09,623 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/019b-horn.smt2 [2018-06-22 01:29:09,630 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:29:09,635 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:29:09,636 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:29:09,636 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:29:09,636 INFO ]: ChcToBoogie initialized [2018-06-22 01:29:09,639 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,694 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09 Unit [2018-06-22 01:29:09,694 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:29:09,695 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:29:09,695 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:29:09,695 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:29:09,715 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,715 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,721 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,721 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,724 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,726 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,727 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... [2018-06-22 01:29:09,729 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:29:09,729 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:29:09,729 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:29:09,729 INFO ]: RCFGBuilder initialized [2018-06-22 01:29:09,730 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 01:29:09,746 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:29:09,746 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:29:09,746 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:29:09,747 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:29:09,747 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:29:09,747 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:29:09,991 INFO ]: Using library mode [2018-06-22 01:29:09,992 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:29:09 BoogieIcfgContainer [2018-06-22 01:29:09,992 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:29:09,993 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:29:09,994 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:29:09,997 INFO ]: TraceAbstraction initialized [2018-06-22 01:29:09,997 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:29:09" (1/3) ... [2018-06-22 01:29:09,998 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6d08d2f0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:29:09, skipping insertion in model container [2018-06-22 01:29:09,998 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:29:09" (2/3) ... [2018-06-22 01:29:09,998 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6d08d2f0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:29:09, skipping insertion in model container [2018-06-22 01:29:09,998 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:29:09" (3/3) ... [2018-06-22 01:29:10,004 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:29:10,014 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:29:10,022 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:29:10,068 INFO ]: Using default assertion order modulation [2018-06-22 01:29:10,069 INFO ]: Interprodecural is true [2018-06-22 01:29:10,069 INFO ]: Hoare is false [2018-06-22 01:29:10,069 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:29:10,069 INFO ]: Backedges is TWOTRACK [2018-06-22 01:29:10,069 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:29:10,069 INFO ]: Difference is false [2018-06-22 01:29:10,069 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:29:10,069 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:29:10,083 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 01:29:10,092 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 01:29:10,092 INFO ]: Found error trace [2018-06-22 01:29:10,093 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:10,093 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:10,097 INFO ]: Analyzing trace with hash -204902306, now seen corresponding path program 1 times [2018-06-22 01:29:10,099 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:10,099 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:10,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:10,131 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:10,131 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:10,184 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:10,313 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:10,314 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:29:10,314 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:29:10,316 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:29:10,326 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:29:10,326 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:29:10,328 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 01:29:10,394 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:10,394 INFO ]: Finished difference Result 9 states and 13 transitions. [2018-06-22 01:29:10,394 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:29:10,395 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 01:29:10,396 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:10,403 INFO ]: With dead ends: 9 [2018-06-22 01:29:10,403 INFO ]: Without dead ends: 9 [2018-06-22 01:29:10,404 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-22 01:29:10,419 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 01:29:10,438 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 01:29:10,440 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 01:29:10,441 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 13 transitions. [2018-06-22 01:29:10,442 INFO ]: Start accepts. Automaton has 9 states and 13 transitions. Word has length 7 [2018-06-22 01:29:10,442 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:10,442 INFO ]: Abstraction has 9 states and 13 transitions. [2018-06-22 01:29:10,442 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:29:10,442 INFO ]: Start isEmpty. Operand 9 states and 13 transitions. [2018-06-22 01:29:10,442 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:29:10,442 INFO ]: Found error trace [2018-06-22 01:29:10,442 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:10,443 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:10,443 INFO ]: Analyzing trace with hash -2054566951, now seen corresponding path program 1 times [2018-06-22 01:29:10,443 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:10,443 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:10,444 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:10,444 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:10,444 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:10,460 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:10,515 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:10,515 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:29:10,515 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:29:10,516 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:29:10,517 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:29:10,517 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:29:10,517 INFO ]: Start difference. First operand 9 states and 13 transitions. Second operand 3 states. [2018-06-22 01:29:10,577 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:10,577 INFO ]: Finished difference Result 10 states and 16 transitions. [2018-06-22 01:29:10,577 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:29:10,577 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:29:10,577 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:10,577 INFO ]: With dead ends: 10 [2018-06-22 01:29:10,577 INFO ]: Without dead ends: 9 [2018-06-22 01:29:10,578 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-22 01:29:10,578 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 01:29:10,579 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 01:29:10,579 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 01:29:10,580 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 11 transitions. [2018-06-22 01:29:10,580 INFO ]: Start accepts. Automaton has 9 states and 11 transitions. Word has length 8 [2018-06-22 01:29:10,580 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:10,580 INFO ]: Abstraction has 9 states and 11 transitions. [2018-06-22 01:29:10,580 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:29:10,580 INFO ]: Start isEmpty. Operand 9 states and 11 transitions. [2018-06-22 01:29:10,580 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:29:10,580 INFO ]: Found error trace [2018-06-22 01:29:10,580 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:10,580 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:10,580 INFO ]: Analyzing trace with hash -2050872867, now seen corresponding path program 1 times [2018-06-22 01:29:10,580 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:10,580 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:10,581 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:10,581 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:10,581 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:10,595 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:10,673 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:10,673 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:10,673 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:10,688 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:10,728 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:10,736 INFO ]: Computing forward predicates... [2018-06-22 01:29:10,830 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:10,849 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:10,849 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 01:29:10,850 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:29:10,850 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:29:10,850 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:29:10,850 INFO ]: Start difference. First operand 9 states and 11 transitions. Second operand 5 states. [2018-06-22 01:29:11,057 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:11,058 INFO ]: Finished difference Result 11 states and 14 transitions. [2018-06-22 01:29:11,059 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:29:11,059 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 01:29:11,059 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:11,059 INFO ]: With dead ends: 11 [2018-06-22 01:29:11,059 INFO ]: Without dead ends: 9 [2018-06-22 01:29:11,059 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:29:11,060 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 01:29:11,061 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 01:29:11,061 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 01:29:11,061 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 10 transitions. [2018-06-22 01:29:11,061 INFO ]: Start accepts. Automaton has 9 states and 10 transitions. Word has length 8 [2018-06-22 01:29:11,061 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:11,061 INFO ]: Abstraction has 9 states and 10 transitions. [2018-06-22 01:29:11,061 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:29:11,061 INFO ]: Start isEmpty. Operand 9 states and 10 transitions. [2018-06-22 01:29:11,061 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:29:11,061 INFO ]: Found error trace [2018-06-22 01:29:11,061 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:11,062 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:11,062 INFO ]: Analyzing trace with hash -2049025825, now seen corresponding path program 1 times [2018-06-22 01:29:11,062 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:11,062 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:11,062 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:11,063 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:11,063 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:11,090 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:11,136 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:11,136 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:29:11,136 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:29:11,136 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:29:11,137 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:29:11,137 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:29:11,137 INFO ]: Start difference. First operand 9 states and 10 transitions. Second operand 3 states. [2018-06-22 01:29:11,174 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:11,174 INFO ]: Finished difference Result 10 states and 12 transitions. [2018-06-22 01:29:11,174 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:29:11,174 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:29:11,175 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:11,175 INFO ]: With dead ends: 10 [2018-06-22 01:29:11,175 INFO ]: Without dead ends: 10 [2018-06-22 01:29:11,175 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-22 01:29:11,175 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 01:29:11,176 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 01:29:11,176 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 01:29:11,177 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 12 transitions. [2018-06-22 01:29:11,177 INFO ]: Start accepts. Automaton has 10 states and 12 transitions. Word has length 8 [2018-06-22 01:29:11,177 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:11,177 INFO ]: Abstraction has 10 states and 12 transitions. [2018-06-22 01:29:11,177 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:29:11,177 INFO ]: Start isEmpty. Operand 10 states and 12 transitions. [2018-06-22 01:29:11,177 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:29:11,177 INFO ]: Found error trace [2018-06-22 01:29:11,177 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:11,178 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:11,178 INFO ]: Analyzing trace with hash 910840188, now seen corresponding path program 1 times [2018-06-22 01:29:11,178 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:11,178 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:11,179 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:11,179 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:11,179 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:11,198 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:11,257 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:29:11,257 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:11,258 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:11,265 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:11,313 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:11,315 INFO ]: Computing forward predicates... [2018-06-22 01:29:11,376 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:29:11,394 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:11,394 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:29:11,395 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:29:11,395 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:29:11,395 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:29:11,395 INFO ]: Start difference. First operand 10 states and 12 transitions. Second operand 4 states. [2018-06-22 01:29:11,448 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:11,448 INFO ]: Finished difference Result 12 states and 16 transitions. [2018-06-22 01:29:11,448 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 01:29:11,448 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 01:29:11,448 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:11,448 INFO ]: With dead ends: 12 [2018-06-22 01:29:11,448 INFO ]: Without dead ends: 12 [2018-06-22 01:29:11,449 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 3 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:29:11,449 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 01:29:11,451 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 01:29:11,451 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 01:29:11,452 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 16 transitions. [2018-06-22 01:29:11,452 INFO ]: Start accepts. Automaton has 12 states and 16 transitions. Word has length 9 [2018-06-22 01:29:11,452 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:11,452 INFO ]: Abstraction has 12 states and 16 transitions. [2018-06-22 01:29:11,452 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:29:11,452 INFO ]: Start isEmpty. Operand 12 states and 16 transitions. [2018-06-22 01:29:11,452 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:29:11,452 INFO ]: Found error trace [2018-06-22 01:29:11,452 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:11,453 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:11,453 INFO ]: Analyzing trace with hash -1822593921, now seen corresponding path program 2 times [2018-06-22 01:29:11,453 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:11,453 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:11,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:11,454 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:11,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:11,493 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:11,728 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:11,729 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:11,729 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:11,755 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:29:11,813 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:29:11,813 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:11,816 INFO ]: Computing forward predicates... [2018-06-22 01:29:12,095 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:12,116 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:12,116 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 01:29:12,116 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:29:12,116 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:29:12,116 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:29:12,117 INFO ]: Start difference. First operand 12 states and 16 transitions. Second operand 8 states. [2018-06-22 01:29:12,295 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 01:29:12,473 WARN ]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 01:29:12,629 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:12,629 INFO ]: Finished difference Result 18 states and 25 transitions. [2018-06-22 01:29:12,630 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:29:12,630 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 01:29:12,630 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:12,630 INFO ]: With dead ends: 18 [2018-06-22 01:29:12,630 INFO ]: Without dead ends: 11 [2018-06-22 01:29:12,631 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:29:12,631 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 01:29:12,632 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 01:29:12,632 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 01:29:12,632 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 13 transitions. [2018-06-22 01:29:12,632 INFO ]: Start accepts. Automaton has 11 states and 13 transitions. Word has length 10 [2018-06-22 01:29:12,632 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:12,632 INFO ]: Abstraction has 11 states and 13 transitions. [2018-06-22 01:29:12,632 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:29:12,632 INFO ]: Start isEmpty. Operand 11 states and 13 transitions. [2018-06-22 01:29:12,633 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:29:12,633 INFO ]: Found error trace [2018-06-22 01:29:12,633 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:12,633 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:12,633 INFO ]: Analyzing trace with hash -1765335619, now seen corresponding path program 3 times [2018-06-22 01:29:12,633 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:12,633 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:12,634 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:12,635 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:12,635 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:12,660 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:12,727 INFO ]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:12,727 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:12,727 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:12,734 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:29:12,760 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 01:29:12,760 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:12,764 INFO ]: Computing forward predicates... [2018-06-22 01:29:13,060 INFO ]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:13,092 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:13,092 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2018-06-22 01:29:13,092 INFO ]: Interpolant automaton has 9 states [2018-06-22 01:29:13,092 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 01:29:13,092 INFO ]: CoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:29:13,093 INFO ]: Start difference. First operand 11 states and 13 transitions. Second operand 9 states. [2018-06-22 01:29:13,261 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:13,261 INFO ]: Finished difference Result 17 states and 25 transitions. [2018-06-22 01:29:13,261 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 01:29:13,261 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-22 01:29:13,261 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:13,262 INFO ]: With dead ends: 17 [2018-06-22 01:29:13,262 INFO ]: Without dead ends: 17 [2018-06-22 01:29:13,262 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=53, Invalid=79, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:29:13,262 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 01:29:13,264 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 01:29:13,264 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 01:29:13,264 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 25 transitions. [2018-06-22 01:29:13,264 INFO ]: Start accepts. Automaton has 17 states and 25 transitions. Word has length 10 [2018-06-22 01:29:13,265 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:13,265 INFO ]: Abstraction has 17 states and 25 transitions. [2018-06-22 01:29:13,265 INFO ]: Interpolant automaton has 9 states. [2018-06-22 01:29:13,265 INFO ]: Start isEmpty. Operand 17 states and 25 transitions. [2018-06-22 01:29:13,267 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:29:13,267 INFO ]: Found error trace [2018-06-22 01:29:13,267 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:13,267 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:13,267 INFO ]: Analyzing trace with hash 1115301982, now seen corresponding path program 4 times [2018-06-22 01:29:13,267 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:13,267 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:13,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:13,268 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:13,268 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:13,293 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:13,358 INFO ]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:29:13,358 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:13,359 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:13,366 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:29:13,386 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:29:13,386 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:13,388 INFO ]: Computing forward predicates... [2018-06-22 01:29:13,393 INFO ]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:29:13,414 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:13,414 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2018-06-22 01:29:13,414 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:29:13,414 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:29:13,414 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:29:13,415 INFO ]: Start difference. First operand 17 states and 25 transitions. Second operand 5 states. [2018-06-22 01:29:13,444 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:13,444 INFO ]: Finished difference Result 28 states and 47 transitions. [2018-06-22 01:29:13,444 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 01:29:13,444 INFO ]: Start accepts. Automaton has 5 states. Word has length 11 [2018-06-22 01:29:13,444 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:13,445 INFO ]: With dead ends: 28 [2018-06-22 01:29:13,445 INFO ]: Without dead ends: 28 [2018-06-22 01:29:13,445 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 11 SyntacticMatches, 3 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:29:13,445 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-22 01:29:13,448 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 28. [2018-06-22 01:29:13,448 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:29:13,449 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 47 transitions. [2018-06-22 01:29:13,449 INFO ]: Start accepts. Automaton has 28 states and 47 transitions. Word has length 11 [2018-06-22 01:29:13,449 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:13,449 INFO ]: Abstraction has 28 states and 47 transitions. [2018-06-22 01:29:13,449 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:29:13,449 INFO ]: Start isEmpty. Operand 28 states and 47 transitions. [2018-06-22 01:29:13,449 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:29:13,449 INFO ]: Found error trace [2018-06-22 01:29:13,450 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:13,450 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:13,450 INFO ]: Analyzing trace with hash 220754397, now seen corresponding path program 5 times [2018-06-22 01:29:13,450 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:13,450 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:13,450 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:13,450 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:13,450 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:13,473 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:13,591 INFO ]: Checked inductivity of 15 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:13,591 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:13,591 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:13,597 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:29:13,670 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 01:29:13,670 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:13,673 INFO ]: Computing forward predicates... [2018-06-22 01:29:14,020 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:14,039 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:14,039 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 01:29:14,040 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:29:14,040 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:29:14,040 INFO ]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:29:14,040 INFO ]: Start difference. First operand 28 states and 47 transitions. Second operand 11 states. [2018-06-22 01:29:14,439 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:14,439 INFO ]: Finished difference Result 37 states and 57 transitions. [2018-06-22 01:29:14,440 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-22 01:29:14,440 INFO ]: Start accepts. Automaton has 11 states. Word has length 12 [2018-06-22 01:29:14,440 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:14,441 INFO ]: With dead ends: 37 [2018-06-22 01:29:14,441 INFO ]: Without dead ends: 18 [2018-06-22 01:29:14,441 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=87, Invalid=255, Unknown=0, NotChecked=0, Total=342 [2018-06-22 01:29:14,441 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-22 01:29:14,443 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-22 01:29:14,443 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-22 01:29:14,444 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 26 transitions. [2018-06-22 01:29:14,444 INFO ]: Start accepts. Automaton has 18 states and 26 transitions. Word has length 12 [2018-06-22 01:29:14,444 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:14,444 INFO ]: Abstraction has 18 states and 26 transitions. [2018-06-22 01:29:14,444 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:29:14,444 INFO ]: Start isEmpty. Operand 18 states and 26 transitions. [2018-06-22 01:29:14,444 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 01:29:14,445 INFO ]: Found error trace [2018-06-22 01:29:14,445 INFO ]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:14,445 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:14,445 INFO ]: Analyzing trace with hash 1745203708, now seen corresponding path program 6 times [2018-06-22 01:29:14,445 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:14,445 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:14,445 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:14,445 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:14,445 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:14,466 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:14,562 INFO ]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:29:14,562 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:14,562 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) [2018-06-22 01:29:14,577 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:14,606 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 01:29:14,606 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:14,609 INFO ]: Computing forward predicates... [2018-06-22 01:29:14,625 INFO ]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:29:14,648 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:14,648 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 01:29:14,649 INFO ]: Interpolant automaton has 6 states [2018-06-22 01:29:14,649 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 01:29:14,649 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:29:14,649 INFO ]: Start difference. First operand 18 states and 26 transitions. Second operand 6 states. [2018-06-22 01:29:14,687 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:14,687 INFO ]: Finished difference Result 37 states and 65 transitions. [2018-06-22 01:29:14,687 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:29:14,687 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 01:29:14,687 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:14,688 INFO ]: With dead ends: 37 [2018-06-22 01:29:14,688 INFO ]: Without dead ends: 37 [2018-06-22 01:29:14,688 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 11 SyntacticMatches, 6 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:29:14,688 INFO ]: Start minimizeSevpa. Operand 37 states. [2018-06-22 01:29:14,692 INFO ]: Finished minimizeSevpa. Reduced states from 37 to 37. [2018-06-22 01:29:14,692 INFO ]: Start removeUnreachable. Operand 37 states. [2018-06-22 01:29:14,693 INFO ]: Finished removeUnreachable. Reduced from 37 states to 37 states and 65 transitions. [2018-06-22 01:29:14,693 INFO ]: Start accepts. Automaton has 37 states and 65 transitions. Word has length 13 [2018-06-22 01:29:14,693 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:14,693 INFO ]: Abstraction has 37 states and 65 transitions. [2018-06-22 01:29:14,693 INFO ]: Interpolant automaton has 6 states. [2018-06-22 01:29:14,693 INFO ]: Start isEmpty. Operand 37 states and 65 transitions. [2018-06-22 01:29:14,694 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:29:14,694 INFO ]: Found error trace [2018-06-22 01:29:14,694 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:14,694 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:14,694 INFO ]: Analyzing trace with hash -1727128577, now seen corresponding path program 7 times [2018-06-22 01:29:14,694 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:14,694 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:14,695 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:14,695 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:14,695 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:14,721 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:14,813 INFO ]: Checked inductivity of 28 backedges. 3 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:14,813 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:14,813 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:14,820 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:14,855 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:14,858 INFO ]: Computing forward predicates... [2018-06-22 01:29:15,062 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:15,094 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:15,094 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-22 01:29:15,094 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:29:15,095 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:29:15,095 INFO ]: CoverageRelationStatistics Valid=44, Invalid=138, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:29:15,095 INFO ]: Start difference. First operand 37 states and 65 transitions. Second operand 14 states. [2018-06-22 01:29:15,886 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:15,886 INFO ]: Finished difference Result 46 states and 67 transitions. [2018-06-22 01:29:15,887 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-22 01:29:15,887 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-22 01:29:15,887 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:15,887 INFO ]: With dead ends: 46 [2018-06-22 01:29:15,887 INFO ]: Without dead ends: 19 [2018-06-22 01:29:15,888 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=190, Invalid=622, Unknown=0, NotChecked=0, Total=812 [2018-06-22 01:29:15,888 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 01:29:15,889 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 01:29:15,889 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 01:29:15,890 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 27 transitions. [2018-06-22 01:29:15,890 INFO ]: Start accepts. Automaton has 19 states and 27 transitions. Word has length 14 [2018-06-22 01:29:15,890 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:15,890 INFO ]: Abstraction has 19 states and 27 transitions. [2018-06-22 01:29:15,890 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:29:15,890 INFO ]: Start isEmpty. Operand 19 states and 27 transitions. [2018-06-22 01:29:15,890 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:29:15,890 INFO ]: Found error trace [2018-06-22 01:29:15,890 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:15,891 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:15,891 INFO ]: Analyzing trace with hash 1758492093, now seen corresponding path program 8 times [2018-06-22 01:29:15,891 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:15,891 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:15,891 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:15,891 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:15,891 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:15,918 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:16,374 INFO ]: Checked inductivity of 28 backedges. 9 proven. 18 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:29:16,374 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:16,374 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:16,381 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:29:16,407 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:29:16,407 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:16,410 INFO ]: Computing forward predicates... [2018-06-22 01:29:16,588 INFO ]: Checked inductivity of 28 backedges. 10 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:16,607 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:16,607 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 16 [2018-06-22 01:29:16,607 INFO ]: Interpolant automaton has 16 states [2018-06-22 01:29:16,607 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 01:29:16,608 INFO ]: CoverageRelationStatistics Valid=75, Invalid=165, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:29:16,608 INFO ]: Start difference. First operand 19 states and 27 transitions. Second operand 16 states. [2018-06-22 01:29:16,950 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:16,950 INFO ]: Finished difference Result 37 states and 63 transitions. [2018-06-22 01:29:16,950 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 01:29:16,950 INFO ]: Start accepts. Automaton has 16 states. Word has length 14 [2018-06-22 01:29:16,950 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:16,951 INFO ]: With dead ends: 37 [2018-06-22 01:29:16,951 INFO ]: Without dead ends: 37 [2018-06-22 01:29:16,952 INFO ]: 0 DeclaredPredicates, 33 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=237, Invalid=465, Unknown=0, NotChecked=0, Total=702 [2018-06-22 01:29:16,952 INFO ]: Start minimizeSevpa. Operand 37 states. [2018-06-22 01:29:16,954 INFO ]: Finished minimizeSevpa. Reduced states from 37 to 27. [2018-06-22 01:29:16,954 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 01:29:16,955 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 43 transitions. [2018-06-22 01:29:16,955 INFO ]: Start accepts. Automaton has 27 states and 43 transitions. Word has length 14 [2018-06-22 01:29:16,955 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:16,955 INFO ]: Abstraction has 27 states and 43 transitions. [2018-06-22 01:29:16,955 INFO ]: Interpolant automaton has 16 states. [2018-06-22 01:29:16,955 INFO ]: Start isEmpty. Operand 27 states and 43 transitions. [2018-06-22 01:29:16,955 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-22 01:29:16,955 INFO ]: Found error trace [2018-06-22 01:29:16,955 INFO ]: trace histogram [4, 4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:16,956 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:16,956 INFO ]: Analyzing trace with hash -1315188642, now seen corresponding path program 9 times [2018-06-22 01:29:16,956 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:16,956 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:16,956 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:16,956 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:16,956 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:16,973 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:17,099 INFO ]: Checked inductivity of 36 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 01:29:17,099 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:17,099 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) [2018-06-22 01:29:17,112 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:17,195 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 01:29:17,195 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:17,197 INFO ]: Computing forward predicates... [2018-06-22 01:29:17,206 INFO ]: Checked inductivity of 36 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 01:29:17,225 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:17,225 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-22 01:29:17,225 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:29:17,225 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:29:17,225 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:29:17,225 INFO ]: Start difference. First operand 27 states and 43 transitions. Second operand 7 states. [2018-06-22 01:29:17,293 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:17,293 INFO ]: Finished difference Result 54 states and 97 transitions. [2018-06-22 01:29:17,293 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 01:29:17,293 INFO ]: Start accepts. Automaton has 7 states. Word has length 15 [2018-06-22 01:29:17,293 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:17,294 INFO ]: With dead ends: 54 [2018-06-22 01:29:17,294 INFO ]: Without dead ends: 54 [2018-06-22 01:29:17,294 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 15 SyntacticMatches, 5 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:29:17,294 INFO ]: Start minimizeSevpa. Operand 54 states. [2018-06-22 01:29:17,297 INFO ]: Finished minimizeSevpa. Reduced states from 54 to 28. [2018-06-22 01:29:17,297 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:29:17,298 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 45 transitions. [2018-06-22 01:29:17,298 INFO ]: Start accepts. Automaton has 28 states and 45 transitions. Word has length 15 [2018-06-22 01:29:17,298 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:17,298 INFO ]: Abstraction has 28 states and 45 transitions. [2018-06-22 01:29:17,298 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:29:17,298 INFO ]: Start isEmpty. Operand 28 states and 45 transitions. [2018-06-22 01:29:17,298 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:29:17,298 INFO ]: Found error trace [2018-06-22 01:29:17,298 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:17,298 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:17,298 INFO ]: Analyzing trace with hash -2110010915, now seen corresponding path program 10 times [2018-06-22 01:29:17,298 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:17,298 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:17,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:17,299 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:17,299 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:17,314 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:17,656 INFO ]: Checked inductivity of 45 backedges. 6 proven. 39 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:17,656 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:17,656 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-22 01:29:17,661 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:29:17,710 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:29:17,710 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:17,714 INFO ]: Computing forward predicates... [2018-06-22 01:29:18,373 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:18,393 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:18,429 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-22 01:29:18,430 INFO ]: Interpolant automaton has 17 states [2018-06-22 01:29:18,430 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 01:29:18,430 INFO ]: CoverageRelationStatistics Valid=62, Invalid=210, Unknown=0, NotChecked=0, Total=272 [2018-06-22 01:29:18,430 INFO ]: Start difference. First operand 28 states and 45 transitions. Second operand 17 states. [2018-06-22 01:29:19,173 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:19,173 INFO ]: Finished difference Result 74 states and 112 transitions. [2018-06-22 01:29:19,174 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-06-22 01:29:19,174 INFO ]: Start accepts. Automaton has 17 states. Word has length 16 [2018-06-22 01:29:19,174 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:19,174 INFO ]: With dead ends: 74 [2018-06-22 01:29:19,174 INFO ]: Without dead ends: 28 [2018-06-22 01:29:19,175 INFO ]: 0 DeclaredPredicates, 51 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 359 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=361, Invalid=1279, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 01:29:19,175 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-22 01:29:19,177 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 28. [2018-06-22 01:29:19,177 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:29:19,179 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 44 transitions. [2018-06-22 01:29:19,179 INFO ]: Start accepts. Automaton has 28 states and 44 transitions. Word has length 16 [2018-06-22 01:29:19,179 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:19,179 INFO ]: Abstraction has 28 states and 44 transitions. [2018-06-22 01:29:19,179 INFO ]: Interpolant automaton has 17 states. [2018-06-22 01:29:19,179 INFO ]: Start isEmpty. Operand 28 states and 44 transitions. [2018-06-22 01:29:19,179 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 01:29:19,179 INFO ]: Found error trace [2018-06-22 01:29:19,179 INFO ]: trace histogram [5, 5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:19,179 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:19,179 INFO ]: Analyzing trace with hash -1372724612, now seen corresponding path program 11 times [2018-06-22 01:29:19,179 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:19,179 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:19,180 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:19,180 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:19,180 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:19,201 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:19,299 INFO ]: Checked inductivity of 55 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 01:29:19,299 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:19,299 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-22 01:29:19,305 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:29:19,341 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 01:29:19,341 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:19,344 INFO ]: Computing forward predicates... [2018-06-22 01:29:19,362 INFO ]: Checked inductivity of 55 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 01:29:19,381 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:19,381 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 01:29:19,381 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:29:19,382 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:29:19,382 INFO ]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:29:19,382 INFO ]: Start difference. First operand 28 states and 44 transitions. Second operand 8 states. [2018-06-22 01:29:19,436 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:19,436 INFO ]: Finished difference Result 71 states and 130 transitions. [2018-06-22 01:29:19,436 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 01:29:19,436 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-22 01:29:19,436 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:19,436 INFO ]: With dead ends: 71 [2018-06-22 01:29:19,436 INFO ]: Without dead ends: 71 [2018-06-22 01:29:19,437 INFO ]: 0 DeclaredPredicates, 30 GetRequests, 16 SyntacticMatches, 7 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:29:19,437 INFO ]: Start minimizeSevpa. Operand 71 states. [2018-06-22 01:29:19,440 INFO ]: Finished minimizeSevpa. Reduced states from 71 to 28. [2018-06-22 01:29:19,440 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-22 01:29:19,440 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 44 transitions. [2018-06-22 01:29:19,440 INFO ]: Start accepts. Automaton has 28 states and 44 transitions. Word has length 17 [2018-06-22 01:29:19,440 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:19,440 INFO ]: Abstraction has 28 states and 44 transitions. [2018-06-22 01:29:19,440 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:29:19,440 INFO ]: Start isEmpty. Operand 28 states and 44 transitions. [2018-06-22 01:29:19,441 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 01:29:19,441 INFO ]: Found error trace [2018-06-22 01:29:19,441 INFO ]: trace histogram [6, 5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:19,441 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:19,441 INFO ]: Analyzing trace with hash 401341311, now seen corresponding path program 12 times [2018-06-22 01:29:19,441 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:19,441 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:19,442 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:19,442 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:19,442 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:19,469 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:19,641 INFO ]: Checked inductivity of 66 backedges. 10 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:19,642 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:19,642 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) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:19,647 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:29:19,689 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 01:29:19,689 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:19,692 INFO ]: Computing forward predicates... [2018-06-22 01:29:19,940 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:19,959 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:19,959 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 01:29:19,959 INFO ]: Interpolant automaton has 20 states [2018-06-22 01:29:19,959 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 01:29:19,960 INFO ]: CoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2018-06-22 01:29:19,960 INFO ]: Start difference. First operand 28 states and 44 transitions. Second operand 20 states. [2018-06-22 01:29:21,182 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:21,182 INFO ]: Finished difference Result 86 states and 125 transitions. [2018-06-22 01:29:21,182 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-06-22 01:29:21,182 INFO ]: Start accepts. Automaton has 20 states. Word has length 18 [2018-06-22 01:29:21,182 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:21,182 INFO ]: With dead ends: 86 [2018-06-22 01:29:21,183 INFO ]: Without dead ends: 29 [2018-06-22 01:29:21,185 INFO ]: 0 DeclaredPredicates, 66 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 731 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=623, Invalid=2347, Unknown=0, NotChecked=0, Total=2970 [2018-06-22 01:29:21,185 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 01:29:21,187 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 01:29:21,187 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 01:29:21,188 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 45 transitions. [2018-06-22 01:29:21,188 INFO ]: Start accepts. Automaton has 29 states and 45 transitions. Word has length 18 [2018-06-22 01:29:21,188 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:21,188 INFO ]: Abstraction has 29 states and 45 transitions. [2018-06-22 01:29:21,188 INFO ]: Interpolant automaton has 20 states. [2018-06-22 01:29:21,188 INFO ]: Start isEmpty. Operand 29 states and 45 transitions. [2018-06-22 01:29:21,188 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-22 01:29:21,188 INFO ]: Found error trace [2018-06-22 01:29:21,189 INFO ]: trace histogram [6, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:21,189 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:21,194 INFO ]: Analyzing trace with hash 263874654, now seen corresponding path program 13 times [2018-06-22 01:29:21,194 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:21,194 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:21,195 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:21,195 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:21,195 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:21,217 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:22,074 INFO ]: Checked inductivity of 78 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:29:22,075 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:22,075 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-22 01:29:22,081 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:22,118 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:22,121 INFO ]: Computing forward predicates... [2018-06-22 01:29:22,139 INFO ]: Checked inductivity of 78 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:29:22,158 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:22,158 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-06-22 01:29:22,158 INFO ]: Interpolant automaton has 9 states [2018-06-22 01:29:22,158 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 01:29:22,158 INFO ]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:29:22,159 INFO ]: Start difference. First operand 29 states and 45 transitions. Second operand 9 states. [2018-06-22 01:29:22,228 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:22,228 INFO ]: Finished difference Result 82 states and 151 transitions. [2018-06-22 01:29:22,228 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 01:29:22,228 INFO ]: Start accepts. Automaton has 9 states. Word has length 19 [2018-06-22 01:29:22,228 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:22,228 INFO ]: With dead ends: 82 [2018-06-22 01:29:22,228 INFO ]: Without dead ends: 82 [2018-06-22 01:29:22,229 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 19 SyntacticMatches, 7 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:29:22,229 INFO ]: Start minimizeSevpa. Operand 82 states. [2018-06-22 01:29:22,235 INFO ]: Finished minimizeSevpa. Reduced states from 82 to 72. [2018-06-22 01:29:22,235 INFO ]: Start removeUnreachable. Operand 72 states. [2018-06-22 01:29:22,236 INFO ]: Finished removeUnreachable. Reduced from 72 states to 72 states and 131 transitions. [2018-06-22 01:29:22,236 INFO ]: Start accepts. Automaton has 72 states and 131 transitions. Word has length 19 [2018-06-22 01:29:22,236 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:22,236 INFO ]: Abstraction has 72 states and 131 transitions. [2018-06-22 01:29:22,236 INFO ]: Interpolant automaton has 9 states. [2018-06-22 01:29:22,236 INFO ]: Start isEmpty. Operand 72 states and 131 transitions. [2018-06-22 01:29:22,237 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-22 01:29:22,237 INFO ]: Found error trace [2018-06-22 01:29:22,237 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:22,237 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:22,237 INFO ]: Analyzing trace with hash -403688995, now seen corresponding path program 14 times [2018-06-22 01:29:22,237 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:22,237 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:22,238 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:22,238 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:22,238 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:22,260 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:22,435 INFO ]: Checked inductivity of 91 backedges. 15 proven. 76 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:22,435 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:22,435 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-22 01:29:22,441 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:29:22,512 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:29:22,512 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:22,516 INFO ]: Computing forward predicates... [2018-06-22 01:29:22,988 INFO ]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:23,008 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:23,008 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 23 [2018-06-22 01:29:23,008 INFO ]: Interpolant automaton has 23 states [2018-06-22 01:29:23,008 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 01:29:23,008 INFO ]: CoverageRelationStatistics Valid=107, Invalid=399, Unknown=0, NotChecked=0, Total=506 [2018-06-22 01:29:23,009 INFO ]: Start difference. First operand 72 states and 131 transitions. Second operand 23 states. [2018-06-22 01:29:24,716 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:24,716 INFO ]: Finished difference Result 101 states and 141 transitions. [2018-06-22 01:29:24,716 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 66 states. [2018-06-22 01:29:24,716 INFO ]: Start accepts. Automaton has 23 states. Word has length 20 [2018-06-22 01:29:24,716 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:24,717 INFO ]: With dead ends: 101 [2018-06-22 01:29:24,717 INFO ]: Without dead ends: 30 [2018-06-22 01:29:24,718 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 7 SyntacticMatches, 7 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1334 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1002, Invalid=3968, Unknown=0, NotChecked=0, Total=4970 [2018-06-22 01:29:24,718 INFO ]: Start minimizeSevpa. Operand 30 states. [2018-06-22 01:29:24,720 INFO ]: Finished minimizeSevpa. Reduced states from 30 to 30. [2018-06-22 01:29:24,720 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-22 01:29:24,721 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 46 transitions. [2018-06-22 01:29:24,721 INFO ]: Start accepts. Automaton has 30 states and 46 transitions. Word has length 20 [2018-06-22 01:29:24,721 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:24,721 INFO ]: Abstraction has 30 states and 46 transitions. [2018-06-22 01:29:24,721 INFO ]: Interpolant automaton has 23 states. [2018-06-22 01:29:24,721 INFO ]: Start isEmpty. Operand 30 states and 46 transitions. [2018-06-22 01:29:24,721 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-22 01:29:24,721 INFO ]: Found error trace [2018-06-22 01:29:24,721 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:24,721 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:24,722 INFO ]: Analyzing trace with hash 297375583, now seen corresponding path program 15 times [2018-06-22 01:29:24,722 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:24,722 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:24,722 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:24,722 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:24,722 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:24,742 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:25,175 INFO ]: Checked inductivity of 91 backedges. 28 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:25,175 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:25,175 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-22 01:29:25,189 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:29:25,241 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-22 01:29:25,241 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:25,245 INFO ]: Computing forward predicates... [2018-06-22 01:29:25,566 INFO ]: Checked inductivity of 91 backedges. 28 proven. 63 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:25,585 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:25,585 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 29 [2018-06-22 01:29:25,585 INFO ]: Interpolant automaton has 29 states [2018-06-22 01:29:25,586 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 01:29:25,586 INFO ]: CoverageRelationStatistics Valid=231, Invalid=581, Unknown=0, NotChecked=0, Total=812 [2018-06-22 01:29:25,586 INFO ]: Start difference. First operand 30 states and 46 transitions. Second operand 29 states. [2018-06-22 01:29:26,870 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:26,870 INFO ]: Finished difference Result 105 states and 196 transitions. [2018-06-22 01:29:26,870 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-06-22 01:29:26,870 INFO ]: Start accepts. Automaton has 29 states. Word has length 20 [2018-06-22 01:29:26,870 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:26,871 INFO ]: With dead ends: 105 [2018-06-22 01:29:26,871 INFO ]: Without dead ends: 105 [2018-06-22 01:29:26,872 INFO ]: 0 DeclaredPredicates, 64 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 917 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1024, Invalid=2398, Unknown=0, NotChecked=0, Total=3422 [2018-06-22 01:29:26,872 INFO ]: Start minimizeSevpa. Operand 105 states. [2018-06-22 01:29:26,880 INFO ]: Finished minimizeSevpa. Reduced states from 105 to 46. [2018-06-22 01:29:26,880 INFO ]: Start removeUnreachable. Operand 46 states. [2018-06-22 01:29:26,881 INFO ]: Finished removeUnreachable. Reduced from 46 states to 46 states and 78 transitions. [2018-06-22 01:29:26,881 INFO ]: Start accepts. Automaton has 46 states and 78 transitions. Word has length 20 [2018-06-22 01:29:26,881 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:26,881 INFO ]: Abstraction has 46 states and 78 transitions. [2018-06-22 01:29:26,881 INFO ]: Interpolant automaton has 29 states. [2018-06-22 01:29:26,881 INFO ]: Start isEmpty. Operand 46 states and 78 transitions. [2018-06-22 01:29:26,881 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 01:29:26,881 INFO ]: Found error trace [2018-06-22 01:29:26,881 INFO ]: trace histogram [7, 7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:26,882 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:26,882 INFO ]: Analyzing trace with hash 634839804, now seen corresponding path program 16 times [2018-06-22 01:29:26,882 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:26,882 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:26,882 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:26,882 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:26,882 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:26,907 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:27,151 INFO ]: Checked inductivity of 105 backedges. 0 proven. 98 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:29:27,151 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:27,151 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-22 01:29:27,157 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:29:27,206 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:29:27,206 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:27,209 INFO ]: Computing forward predicates... [2018-06-22 01:29:27,228 INFO ]: Checked inductivity of 105 backedges. 0 proven. 98 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:29:27,246 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:27,247 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 01:29:27,247 INFO ]: Interpolant automaton has 10 states [2018-06-22 01:29:27,247 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 01:29:27,247 INFO ]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:29:27,247 INFO ]: Start difference. First operand 46 states and 78 transitions. Second operand 10 states. [2018-06-22 01:29:27,339 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:27,339 INFO ]: Finished difference Result 108 states and 202 transitions. [2018-06-22 01:29:27,339 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:29:27,339 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 01:29:27,339 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:27,340 INFO ]: With dead ends: 108 [2018-06-22 01:29:27,340 INFO ]: Without dead ends: 108 [2018-06-22 01:29:27,340 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 17 SyntacticMatches, 12 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:29:27,340 INFO ]: Start minimizeSevpa. Operand 108 states. [2018-06-22 01:29:27,344 INFO ]: Finished minimizeSevpa. Reduced states from 108 to 48. [2018-06-22 01:29:27,344 INFO ]: Start removeUnreachable. Operand 48 states. [2018-06-22 01:29:27,345 INFO ]: Finished removeUnreachable. Reduced from 48 states to 48 states and 82 transitions. [2018-06-22 01:29:27,345 INFO ]: Start accepts. Automaton has 48 states and 82 transitions. Word has length 21 [2018-06-22 01:29:27,345 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:27,345 INFO ]: Abstraction has 48 states and 82 transitions. [2018-06-22 01:29:27,345 INFO ]: Interpolant automaton has 10 states. [2018-06-22 01:29:27,345 INFO ]: Start isEmpty. Operand 48 states and 82 transitions. [2018-06-22 01:29:27,346 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-22 01:29:27,346 INFO ]: Found error trace [2018-06-22 01:29:27,346 INFO ]: trace histogram [8, 7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:27,346 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:27,346 INFO ]: Analyzing trace with hash -1788671233, now seen corresponding path program 17 times [2018-06-22 01:29:27,346 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:27,346 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:27,347 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:27,347 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:27,347 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:27,370 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:27,576 INFO ]: Checked inductivity of 120 backedges. 21 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:27,576 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:27,576 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:27,581 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:29:27,655 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-22 01:29:27,655 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:27,659 INFO ]: Computing forward predicates... [2018-06-22 01:29:28,464 INFO ]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:28,483 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:28,483 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 26 [2018-06-22 01:29:28,483 INFO ]: Interpolant automaton has 26 states [2018-06-22 01:29:28,484 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 01:29:28,484 INFO ]: CoverageRelationStatistics Valid=134, Invalid=516, Unknown=0, NotChecked=0, Total=650 [2018-06-22 01:29:28,484 INFO ]: Start difference. First operand 48 states and 82 transitions. Second operand 26 states. [2018-06-22 01:29:31,246 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 17 [2018-06-22 01:29:31,710 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:31,710 INFO ]: Finished difference Result 159 states and 233 transitions. [2018-06-22 01:29:31,710 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-06-22 01:29:31,710 INFO ]: Start accepts. Automaton has 26 states. Word has length 22 [2018-06-22 01:29:31,710 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:31,711 INFO ]: With dead ends: 159 [2018-06-22 01:29:31,711 INFO ]: Without dead ends: 47 [2018-06-22 01:29:31,712 INFO ]: 0 DeclaredPredicates, 102 GetRequests, 7 SyntacticMatches, 8 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2248 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=1527, Invalid=6305, Unknown=0, NotChecked=0, Total=7832 [2018-06-22 01:29:31,712 INFO ]: Start minimizeSevpa. Operand 47 states. [2018-06-22 01:29:31,714 INFO ]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-06-22 01:29:31,714 INFO ]: Start removeUnreachable. Operand 47 states. [2018-06-22 01:29:31,715 INFO ]: Finished removeUnreachable. Reduced from 47 states to 47 states and 79 transitions. [2018-06-22 01:29:31,715 INFO ]: Start accepts. Automaton has 47 states and 79 transitions. Word has length 22 [2018-06-22 01:29:31,715 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:31,715 INFO ]: Abstraction has 47 states and 79 transitions. [2018-06-22 01:29:31,715 INFO ]: Interpolant automaton has 26 states. [2018-06-22 01:29:31,715 INFO ]: Start isEmpty. Operand 47 states and 79 transitions. [2018-06-22 01:29:31,716 INFO ]: Finished isEmpty. Found accepting run of length 24 [2018-06-22 01:29:31,716 INFO ]: Found error trace [2018-06-22 01:29:31,716 INFO ]: trace histogram [8, 8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:31,716 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:31,716 INFO ]: Analyzing trace with hash -194908066, now seen corresponding path program 18 times [2018-06-22 01:29:31,716 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:31,716 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:31,717 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:31,717 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:31,717 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:31,741 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:32,370 INFO ]: Checked inductivity of 136 backedges. 0 proven. 128 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 01:29:32,370 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:32,370 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:32,380 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:29:32,437 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2018-06-22 01:29:32,437 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:32,441 INFO ]: Computing forward predicates... [2018-06-22 01:29:32,469 INFO ]: Checked inductivity of 136 backedges. 0 proven. 128 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 01:29:32,494 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:32,494 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 11 [2018-06-22 01:29:32,494 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:29:32,494 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:29:32,494 INFO ]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:29:32,494 INFO ]: Start difference. First operand 47 states and 79 transitions. Second operand 11 states. [2018-06-22 01:29:32,608 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:32,608 INFO ]: Finished difference Result 126 states and 237 transitions. [2018-06-22 01:29:32,608 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 01:29:32,608 INFO ]: Start accepts. Automaton has 11 states. Word has length 23 [2018-06-22 01:29:32,609 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:32,609 INFO ]: With dead ends: 126 [2018-06-22 01:29:32,609 INFO ]: Without dead ends: 126 [2018-06-22 01:29:32,610 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 12 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:29:32,610 INFO ]: Start minimizeSevpa. Operand 126 states. [2018-06-22 01:29:32,615 INFO ]: Finished minimizeSevpa. Reduced states from 126 to 48. [2018-06-22 01:29:32,615 INFO ]: Start removeUnreachable. Operand 48 states. [2018-06-22 01:29:32,616 INFO ]: Finished removeUnreachable. Reduced from 48 states to 48 states and 81 transitions. [2018-06-22 01:29:32,616 INFO ]: Start accepts. Automaton has 48 states and 81 transitions. Word has length 23 [2018-06-22 01:29:32,616 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:32,616 INFO ]: Abstraction has 48 states and 81 transitions. [2018-06-22 01:29:32,616 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:29:32,616 INFO ]: Start isEmpty. Operand 48 states and 81 transitions. [2018-06-22 01:29:32,617 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-22 01:29:32,617 INFO ]: Found error trace [2018-06-22 01:29:32,617 INFO ]: trace histogram [9, 8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:32,617 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:32,617 INFO ]: Analyzing trace with hash -1741051427, now seen corresponding path program 19 times [2018-06-22 01:29:32,617 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:32,617 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:32,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:32,618 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:32,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:32,653 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:32,976 INFO ]: Checked inductivity of 153 backedges. 28 proven. 125 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:32,976 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:32,976 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:32,982 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:33,047 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:33,053 INFO ]: Computing forward predicates... [2018-06-22 01:29:34,113 INFO ]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:34,132 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:34,132 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 29 [2018-06-22 01:29:34,132 INFO ]: Interpolant automaton has 29 states [2018-06-22 01:29:34,132 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 01:29:34,132 INFO ]: CoverageRelationStatistics Valid=164, Invalid=648, Unknown=0, NotChecked=0, Total=812 [2018-06-22 01:29:34,132 INFO ]: Start difference. First operand 48 states and 81 transitions. Second operand 29 states. [2018-06-22 01:29:34,690 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 13 [2018-06-22 01:29:37,695 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:37,696 INFO ]: Finished difference Result 174 states and 248 transitions. [2018-06-22 01:29:37,696 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 102 states. [2018-06-22 01:29:37,696 INFO ]: Start accepts. Automaton has 29 states. Word has length 24 [2018-06-22 01:29:37,696 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:37,696 INFO ]: With dead ends: 174 [2018-06-22 01:29:37,696 INFO ]: Without dead ends: 48 [2018-06-22 01:29:37,699 INFO ]: 0 DeclaredPredicates, 123 GetRequests, 7 SyntacticMatches, 9 SemanticMatches, 107 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3565 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=2230, Invalid=9542, Unknown=0, NotChecked=0, Total=11772 [2018-06-22 01:29:37,699 INFO ]: Start minimizeSevpa. Operand 48 states. [2018-06-22 01:29:37,702 INFO ]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-06-22 01:29:37,702 INFO ]: Start removeUnreachable. Operand 48 states. [2018-06-22 01:29:37,703 INFO ]: Finished removeUnreachable. Reduced from 48 states to 48 states and 80 transitions. [2018-06-22 01:29:37,703 INFO ]: Start accepts. Automaton has 48 states and 80 transitions. Word has length 24 [2018-06-22 01:29:37,703 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:37,703 INFO ]: Abstraction has 48 states and 80 transitions. [2018-06-22 01:29:37,703 INFO ]: Interpolant automaton has 29 states. [2018-06-22 01:29:37,703 INFO ]: Start isEmpty. Operand 48 states and 80 transitions. [2018-06-22 01:29:37,704 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 01:29:37,704 INFO ]: Found error trace [2018-06-22 01:29:37,704 INFO ]: trace histogram [9, 9, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:37,704 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:37,704 INFO ]: Analyzing trace with hash 856994684, now seen corresponding path program 20 times [2018-06-22 01:29:37,704 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:37,704 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:37,708 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:37,708 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:37,708 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:37,731 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:37,920 INFO ]: Checked inductivity of 171 backedges. 0 proven. 162 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:29:37,920 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:37,920 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:37,926 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:29:37,983 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:29:37,983 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:37,987 INFO ]: Computing forward predicates... [2018-06-22 01:29:38,009 INFO ]: Checked inductivity of 171 backedges. 0 proven. 162 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:29:38,029 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:38,029 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-06-22 01:29:38,029 INFO ]: Interpolant automaton has 12 states [2018-06-22 01:29:38,029 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 01:29:38,029 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:29:38,029 INFO ]: Start difference. First operand 48 states and 80 transitions. Second operand 12 states. [2018-06-22 01:29:38,136 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:38,136 INFO ]: Finished difference Result 153 states and 290 transitions. [2018-06-22 01:29:38,136 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 01:29:38,137 INFO ]: Start accepts. Automaton has 12 states. Word has length 25 [2018-06-22 01:29:38,137 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:38,137 INFO ]: With dead ends: 153 [2018-06-22 01:29:38,137 INFO ]: Without dead ends: 153 [2018-06-22 01:29:38,138 INFO ]: 0 DeclaredPredicates, 46 GetRequests, 21 SyntacticMatches, 14 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:29:38,138 INFO ]: Start minimizeSevpa. Operand 153 states. [2018-06-22 01:29:38,141 INFO ]: Finished minimizeSevpa. Reduced states from 153 to 48. [2018-06-22 01:29:38,141 INFO ]: Start removeUnreachable. Operand 48 states. [2018-06-22 01:29:38,141 INFO ]: Finished removeUnreachable. Reduced from 48 states to 48 states and 80 transitions. [2018-06-22 01:29:38,141 INFO ]: Start accepts. Automaton has 48 states and 80 transitions. Word has length 25 [2018-06-22 01:29:38,142 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:38,142 INFO ]: Abstraction has 48 states and 80 transitions. [2018-06-22 01:29:38,142 INFO ]: Interpolant automaton has 12 states. [2018-06-22 01:29:38,142 INFO ]: Start isEmpty. Operand 48 states and 80 transitions. [2018-06-22 01:29:38,142 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-22 01:29:38,142 INFO ]: Found error trace [2018-06-22 01:29:38,142 INFO ]: trace histogram [10, 9, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:38,142 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:38,142 INFO ]: Analyzing trace with hash 803162751, now seen corresponding path program 21 times [2018-06-22 01:29:38,142 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:38,143 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:38,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:38,143 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:38,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:38,166 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:38,802 INFO ]: Checked inductivity of 190 backedges. 36 proven. 154 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:38,802 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:38,802 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 01:29:38,818 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:38,953 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2018-06-22 01:29:38,953 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:38,957 INFO ]: Computing forward predicates... [2018-06-22 01:29:39,320 INFO ]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:39,340 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:39,340 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 32 [2018-06-22 01:29:39,340 INFO ]: Interpolant automaton has 32 states [2018-06-22 01:29:39,340 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 01:29:39,340 INFO ]: CoverageRelationStatistics Valid=197, Invalid=795, Unknown=0, NotChecked=0, Total=992 [2018-06-22 01:29:39,340 INFO ]: Start difference. First operand 48 states and 80 transitions. Second operand 32 states. [2018-06-22 01:29:44,013 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:44,013 INFO ]: Finished difference Result 190 states and 265 transitions. [2018-06-22 01:29:44,013 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 123 states. [2018-06-22 01:29:44,013 INFO ]: Start accepts. Automaton has 32 states. Word has length 26 [2018-06-22 01:29:44,013 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:44,014 INFO ]: With dead ends: 190 [2018-06-22 01:29:44,014 INFO ]: Without dead ends: 49 [2018-06-22 01:29:44,016 INFO ]: 0 DeclaredPredicates, 146 GetRequests, 7 SyntacticMatches, 10 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5389 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=3146, Invalid=13884, Unknown=0, NotChecked=0, Total=17030 [2018-06-22 01:29:44,017 INFO ]: Start minimizeSevpa. Operand 49 states. [2018-06-22 01:29:44,018 INFO ]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-06-22 01:29:44,018 INFO ]: Start removeUnreachable. Operand 49 states. [2018-06-22 01:29:44,019 INFO ]: Finished removeUnreachable. Reduced from 49 states to 49 states and 81 transitions. [2018-06-22 01:29:44,019 INFO ]: Start accepts. Automaton has 49 states and 81 transitions. Word has length 26 [2018-06-22 01:29:44,019 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:44,019 INFO ]: Abstraction has 49 states and 81 transitions. [2018-06-22 01:29:44,019 INFO ]: Interpolant automaton has 32 states. [2018-06-22 01:29:44,019 INFO ]: Start isEmpty. Operand 49 states and 81 transitions. [2018-06-22 01:29:44,020 INFO ]: Finished isEmpty. Found accepting run of length 28 [2018-06-22 01:29:44,020 INFO ]: Found error trace [2018-06-22 01:29:44,020 INFO ]: trace histogram [10, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:44,020 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:44,020 INFO ]: Analyzing trace with hash -2145490850, now seen corresponding path program 22 times [2018-06-22 01:29:44,020 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:44,020 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:44,021 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:44,021 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:44,021 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:44,058 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:44,313 INFO ]: Checked inductivity of 210 backedges. 0 proven. 200 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:29:44,313 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:44,313 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:44,319 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:29:44,372 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:29:44,372 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:44,377 INFO ]: Computing forward predicates... [2018-06-22 01:29:44,403 INFO ]: Checked inductivity of 210 backedges. 0 proven. 200 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:29:44,422 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:44,422 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2018-06-22 01:29:44,422 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:29:44,422 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:29:44,422 INFO ]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:29:44,422 INFO ]: Start difference. First operand 49 states and 81 transitions. Second operand 13 states. [2018-06-22 01:29:44,638 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:44,638 INFO ]: Finished difference Result 173 states and 329 transitions. [2018-06-22 01:29:44,638 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 01:29:44,638 INFO ]: Start accepts. Automaton has 13 states. Word has length 27 [2018-06-22 01:29:44,638 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:44,639 INFO ]: With dead ends: 173 [2018-06-22 01:29:44,639 INFO ]: Without dead ends: 173 [2018-06-22 01:29:44,640 INFO ]: 0 DeclaredPredicates, 50 GetRequests, 24 SyntacticMatches, 14 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:29:44,640 INFO ]: Start minimizeSevpa. Operand 173 states. [2018-06-22 01:29:44,649 INFO ]: Finished minimizeSevpa. Reduced states from 173 to 170. [2018-06-22 01:29:44,649 INFO ]: Start removeUnreachable. Operand 170 states. [2018-06-22 01:29:44,650 INFO ]: Finished removeUnreachable. Reduced from 170 states to 170 states and 323 transitions. [2018-06-22 01:29:44,650 INFO ]: Start accepts. Automaton has 170 states and 323 transitions. Word has length 27 [2018-06-22 01:29:44,651 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:44,651 INFO ]: Abstraction has 170 states and 323 transitions. [2018-06-22 01:29:44,651 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:29:44,651 INFO ]: Start isEmpty. Operand 170 states and 323 transitions. [2018-06-22 01:29:44,652 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-22 01:29:44,652 INFO ]: Found error trace [2018-06-22 01:29:44,652 INFO ]: trace histogram [11, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:44,652 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:44,652 INFO ]: Analyzing trace with hash -2079575587, now seen corresponding path program 23 times [2018-06-22 01:29:44,652 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:44,652 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:44,653 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:44,653 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:44,653 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:44,675 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:44,953 INFO ]: Checked inductivity of 231 backedges. 45 proven. 186 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:44,953 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:44,953 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:44,961 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:29:45,032 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 01:29:45,032 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:45,037 INFO ]: Computing forward predicates... [2018-06-22 01:29:45,463 INFO ]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:45,483 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:45,483 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 35 [2018-06-22 01:29:45,483 INFO ]: Interpolant automaton has 35 states [2018-06-22 01:29:45,483 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 01:29:45,484 INFO ]: CoverageRelationStatistics Valid=233, Invalid=957, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:29:45,484 INFO ]: Start difference. First operand 170 states and 323 transitions. Second operand 35 states. [2018-06-22 01:29:51,787 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:51,787 INFO ]: Finished difference Result 213 states and 289 transitions. [2018-06-22 01:29:51,787 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 146 states. [2018-06-22 01:29:51,787 INFO ]: Start accepts. Automaton has 35 states. Word has length 28 [2018-06-22 01:29:51,787 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:51,787 INFO ]: With dead ends: 213 [2018-06-22 01:29:51,787 INFO ]: Without dead ends: 50 [2018-06-22 01:29:51,791 INFO ]: 0 DeclaredPredicates, 171 GetRequests, 7 SyntacticMatches, 11 SemanticMatches, 153 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7836 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=4313, Invalid=19557, Unknown=0, NotChecked=0, Total=23870 [2018-06-22 01:29:51,791 INFO ]: Start minimizeSevpa. Operand 50 states. [2018-06-22 01:29:51,793 INFO ]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-06-22 01:29:51,793 INFO ]: Start removeUnreachable. Operand 50 states. [2018-06-22 01:29:51,793 INFO ]: Finished removeUnreachable. Reduced from 50 states to 50 states and 82 transitions. [2018-06-22 01:29:51,794 INFO ]: Start accepts. Automaton has 50 states and 82 transitions. Word has length 28 [2018-06-22 01:29:51,794 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:51,794 INFO ]: Abstraction has 50 states and 82 transitions. [2018-06-22 01:29:51,794 INFO ]: Interpolant automaton has 35 states. [2018-06-22 01:29:51,794 INFO ]: Start isEmpty. Operand 50 states and 82 transitions. [2018-06-22 01:29:51,794 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-22 01:29:51,794 INFO ]: Found error trace [2018-06-22 01:29:51,794 INFO ]: trace histogram [11, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:51,794 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:51,795 INFO ]: Analyzing trace with hash 935528031, now seen corresponding path program 24 times [2018-06-22 01:29:51,795 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:51,795 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:51,795 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:51,795 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:51,795 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:51,818 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:52,652 INFO ]: Checked inductivity of 231 backedges. 121 proven. 101 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:29:52,652 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:52,652 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:52,658 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:29:52,726 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2018-06-22 01:29:52,726 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:52,731 INFO ]: Computing forward predicates... [2018-06-22 01:29:53,416 INFO ]: Checked inductivity of 231 backedges. 176 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:53,435 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:53,435 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 23] total 35 [2018-06-22 01:29:53,436 INFO ]: Interpolant automaton has 35 states [2018-06-22 01:29:53,436 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 01:29:53,436 INFO ]: CoverageRelationStatistics Valid=365, Invalid=825, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:29:53,436 INFO ]: Start difference. First operand 50 states and 82 transitions. Second operand 35 states. [2018-06-22 01:29:56,802 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:56,802 INFO ]: Finished difference Result 166 states and 314 transitions. [2018-06-22 01:29:56,802 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2018-06-22 01:29:56,802 INFO ]: Start accepts. Automaton has 35 states. Word has length 28 [2018-06-22 01:29:56,802 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:56,803 INFO ]: With dead ends: 166 [2018-06-22 01:29:56,803 INFO ]: Without dead ends: 166 [2018-06-22 01:29:56,805 INFO ]: 0 DeclaredPredicates, 135 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 118 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3850 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=4464, Invalid=9816, Unknown=0, NotChecked=0, Total=14280 [2018-06-22 01:29:56,805 INFO ]: Start minimizeSevpa. Operand 166 states. [2018-06-22 01:29:56,811 INFO ]: Finished minimizeSevpa. Reduced states from 166 to 90. [2018-06-22 01:29:56,811 INFO ]: Start removeUnreachable. Operand 90 states. [2018-06-22 01:29:56,812 INFO ]: Finished removeUnreachable. Reduced from 90 states to 90 states and 162 transitions. [2018-06-22 01:29:56,812 INFO ]: Start accepts. Automaton has 90 states and 162 transitions. Word has length 28 [2018-06-22 01:29:56,812 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:56,812 INFO ]: Abstraction has 90 states and 162 transitions. [2018-06-22 01:29:56,812 INFO ]: Interpolant automaton has 35 states. [2018-06-22 01:29:56,812 INFO ]: Start isEmpty. Operand 90 states and 162 transitions. [2018-06-22 01:29:56,813 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 01:29:56,813 INFO ]: Found error trace [2018-06-22 01:29:56,813 INFO ]: trace histogram [11, 11, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:56,813 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:56,813 INFO ]: Analyzing trace with hash -1057270788, now seen corresponding path program 25 times [2018-06-22 01:29:56,813 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:56,813 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:56,813 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:56,813 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:29:56,813 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:56,842 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:57,660 INFO ]: Checked inductivity of 253 backedges. 0 proven. 242 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 01:29:57,660 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:57,681 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:57,687 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:57,747 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:57,751 INFO ]: Computing forward predicates... [2018-06-22 01:29:57,840 INFO ]: Checked inductivity of 253 backedges. 0 proven. 242 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 01:29:57,861 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:57,862 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 14 [2018-06-22 01:29:57,862 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:29:57,862 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:29:57,862 INFO ]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:29:57,862 INFO ]: Start difference. First operand 90 states and 162 transitions. Second operand 14 states. [2018-06-22 01:29:58,010 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:29:58,011 INFO ]: Finished difference Result 255 states and 492 transitions. [2018-06-22 01:29:58,011 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 01:29:58,011 INFO ]: Start accepts. Automaton has 14 states. Word has length 29 [2018-06-22 01:29:58,011 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:29:58,012 INFO ]: With dead ends: 255 [2018-06-22 01:29:58,012 INFO ]: Without dead ends: 255 [2018-06-22 01:29:58,012 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 26 SyntacticMatches, 15 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:29:58,012 INFO ]: Start minimizeSevpa. Operand 255 states. [2018-06-22 01:29:58,017 INFO ]: Finished minimizeSevpa. Reduced states from 255 to 94. [2018-06-22 01:29:58,017 INFO ]: Start removeUnreachable. Operand 94 states. [2018-06-22 01:29:58,018 INFO ]: Finished removeUnreachable. Reduced from 94 states to 94 states and 170 transitions. [2018-06-22 01:29:58,018 INFO ]: Start accepts. Automaton has 94 states and 170 transitions. Word has length 29 [2018-06-22 01:29:58,018 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:29:58,018 INFO ]: Abstraction has 94 states and 170 transitions. [2018-06-22 01:29:58,018 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:29:58,018 INFO ]: Start isEmpty. Operand 94 states and 170 transitions. [2018-06-22 01:29:58,018 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-22 01:29:58,018 INFO ]: Found error trace [2018-06-22 01:29:58,018 INFO ]: trace histogram [12, 11, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:29:58,018 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:29:58,019 INFO ]: Analyzing trace with hash 1590475263, now seen corresponding path program 26 times [2018-06-22 01:29:58,019 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:29:58,019 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:29:58,019 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:58,019 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:29:58,019 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:29:58,041 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:58,341 INFO ]: Checked inductivity of 276 backedges. 55 proven. 221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:58,341 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:29:58,341 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:29:58,352 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:29:58,414 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:29:58,414 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:29:58,418 INFO ]: Computing forward predicates... [2018-06-22 01:29:58,920 INFO ]: Checked inductivity of 276 backedges. 0 proven. 276 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:29:58,940 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:29:58,940 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 38 [2018-06-22 01:29:58,940 INFO ]: Interpolant automaton has 38 states [2018-06-22 01:29:58,940 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-22 01:29:58,940 INFO ]: CoverageRelationStatistics Valid=272, Invalid=1134, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 01:29:58,940 INFO ]: Start difference. First operand 94 states and 170 transitions. Second operand 38 states. [2018-06-22 01:30:07,112 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:07,112 INFO ]: Finished difference Result 345 states and 505 transitions. [2018-06-22 01:30:07,112 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 171 states. [2018-06-22 01:30:07,112 INFO ]: Start accepts. Automaton has 38 states. Word has length 30 [2018-06-22 01:30:07,112 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:07,112 INFO ]: With dead ends: 345 [2018-06-22 01:30:07,112 INFO ]: Without dead ends: 91 [2018-06-22 01:30:07,114 INFO ]: 0 DeclaredPredicates, 198 GetRequests, 7 SyntacticMatches, 12 SemanticMatches, 179 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11034 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=5772, Invalid=26808, Unknown=0, NotChecked=0, Total=32580 [2018-06-22 01:30:07,114 INFO ]: Start minimizeSevpa. Operand 91 states. [2018-06-22 01:30:07,117 INFO ]: Finished minimizeSevpa. Reduced states from 91 to 91. [2018-06-22 01:30:07,117 INFO ]: Start removeUnreachable. Operand 91 states. [2018-06-22 01:30:07,118 INFO ]: Finished removeUnreachable. Reduced from 91 states to 91 states and 163 transitions. [2018-06-22 01:30:07,118 INFO ]: Start accepts. Automaton has 91 states and 163 transitions. Word has length 30 [2018-06-22 01:30:07,118 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:07,118 INFO ]: Abstraction has 91 states and 163 transitions. [2018-06-22 01:30:07,118 INFO ]: Interpolant automaton has 38 states. [2018-06-22 01:30:07,118 INFO ]: Start isEmpty. Operand 91 states and 163 transitions. [2018-06-22 01:30:07,118 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-22 01:30:07,118 INFO ]: Found error trace [2018-06-22 01:30:07,118 INFO ]: trace histogram [12, 12, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:07,118 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:07,119 INFO ]: Analyzing trace with hash 477876318, now seen corresponding path program 27 times [2018-06-22 01:30:07,119 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:07,120 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:07,120 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:07,120 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:07,120 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:07,149 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:07,505 INFO ]: Checked inductivity of 300 backedges. 0 proven. 288 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-06-22 01:30:07,505 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:07,505 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:07,511 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:30:07,590 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 13 check-sat command(s) [2018-06-22 01:30:07,590 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:07,595 INFO ]: Computing forward predicates... [2018-06-22 01:30:07,654 INFO ]: Checked inductivity of 300 backedges. 0 proven. 288 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-06-22 01:30:07,673 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:07,673 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 15 [2018-06-22 01:30:07,673 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:30:07,673 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:30:07,673 INFO ]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:30:07,673 INFO ]: Start difference. First operand 91 states and 163 transitions. Second operand 15 states. [2018-06-22 01:30:07,843 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:07,843 INFO ]: Finished difference Result 291 states and 563 transitions. [2018-06-22 01:30:07,923 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 01:30:07,923 INFO ]: Start accepts. Automaton has 15 states. Word has length 31 [2018-06-22 01:30:07,923 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:07,924 INFO ]: With dead ends: 291 [2018-06-22 01:30:07,924 INFO ]: Without dead ends: 291 [2018-06-22 01:30:07,924 INFO ]: 0 DeclaredPredicates, 58 GetRequests, 26 SyntacticMatches, 18 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:30:07,924 INFO ]: Start minimizeSevpa. Operand 291 states. [2018-06-22 01:30:07,929 INFO ]: Finished minimizeSevpa. Reduced states from 291 to 94. [2018-06-22 01:30:07,929 INFO ]: Start removeUnreachable. Operand 94 states. [2018-06-22 01:30:07,930 INFO ]: Finished removeUnreachable. Reduced from 94 states to 94 states and 169 transitions. [2018-06-22 01:30:07,930 INFO ]: Start accepts. Automaton has 94 states and 169 transitions. Word has length 31 [2018-06-22 01:30:07,930 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:07,930 INFO ]: Abstraction has 94 states and 169 transitions. [2018-06-22 01:30:07,930 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:30:07,930 INFO ]: Start isEmpty. Operand 94 states and 169 transitions. [2018-06-22 01:30:07,930 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-22 01:30:07,930 INFO ]: Found error trace [2018-06-22 01:30:07,930 INFO ]: trace histogram [13, 12, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:07,930 INFO ]: === Iteration 32 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:07,930 INFO ]: Analyzing trace with hash 1935395293, now seen corresponding path program 28 times [2018-06-22 01:30:07,931 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:07,931 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:07,931 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:07,931 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:07,931 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:07,957 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:09,188 INFO ]: Checked inductivity of 325 backedges. 66 proven. 259 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:09,188 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:09,188 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:09,194 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:30:09,261 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:30:09,261 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:09,267 INFO ]: Computing forward predicates... [2018-06-22 01:30:10,079 INFO ]: Checked inductivity of 325 backedges. 0 proven. 325 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:10,098 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:10,098 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 41 [2018-06-22 01:30:10,098 INFO ]: Interpolant automaton has 41 states [2018-06-22 01:30:10,098 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 01:30:10,098 INFO ]: CoverageRelationStatistics Valid=314, Invalid=1326, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 01:30:10,098 INFO ]: Start difference. First operand 94 states and 169 transitions. Second operand 41 states. Received shutdown request... [2018-06-22 01:30:11,356 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-06-22 01:30:11,356 WARN ]: Verification canceled [2018-06-22 01:30:11,361 WARN ]: Timeout [2018-06-22 01:30:11,361 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:30:11 BoogieIcfgContainer [2018-06-22 01:30:11,361 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:30:11,362 INFO ]: Toolchain (without parser) took 61731.13 ms. Allocated memory was 303.0 MB in the beginning and 674.8 MB in the end (delta: 371.7 MB). Free memory was 259.6 MB in the beginning and 291.3 MB in the end (delta: -31.7 MB). Peak memory consumption was 340.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:30:11,363 INFO ]: SmtParser took 0.09 ms. Allocated memory is still 303.0 MB. Free memory is still 268.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:30:11,363 INFO ]: ChcToBoogie took 59.06 ms. Allocated memory is still 303.0 MB. Free memory was 259.6 MB in the beginning and 257.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:30:11,363 INFO ]: Boogie Preprocessor took 33.83 ms. Allocated memory is still 303.0 MB. Free memory was 257.6 MB in the beginning and 255.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:30:11,364 INFO ]: RCFGBuilder took 262.90 ms. Allocated memory is still 303.0 MB. Free memory was 255.6 MB in the beginning and 247.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:30:11,364 INFO ]: TraceAbstraction took 61367.73 ms. Allocated memory was 303.0 MB in the beginning and 674.8 MB in the end (delta: 371.7 MB). Free memory was 246.6 MB in the beginning and 291.3 MB in the end (delta: -44.7 MB). Peak memory consumption was 327.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:30:11,366 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.09 ms. Allocated memory is still 303.0 MB. Free memory is still 268.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 59.06 ms. Allocated memory is still 303.0 MB. Free memory was 259.6 MB in the beginning and 257.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 33.83 ms. Allocated memory is still 303.0 MB. Free memory was 257.6 MB in the beginning and 255.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 262.90 ms. Allocated memory is still 303.0 MB. Free memory was 255.6 MB in the beginning and 247.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61367.73 ms. Allocated memory was 303.0 MB in the beginning and 674.8 MB in the end (delta: 371.7 MB). Free memory was 246.6 MB in the beginning and 291.3 MB in the end (delta: -44.7 MB). Peak memory consumption was 327.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (94states) and interpolant automaton (currently 61 states, 41 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 73 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 61.3s OverallTime, 32 OverallIterations, 13 TraceHistogramMax, 39.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 226 SDtfs, 180 SDslu, 1169 SDs, 0 SdLazy, 5928 SolverSat, 1611 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 5.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1815 GetRequests, 350 SyntacticMatches, 207 SemanticMatches, 1257 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38723 ImplicationChecksByTransitivity, 48.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=170occurred in iteration=26, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 31 MinimizatonAttempts, 828 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 2.0s SatisfiabilityAnalysisTime, 18.2s InterpolantComputationTime, 1167 NumberOfCodeBlocks, 1167 NumberOfCodeBlocksAsserted, 156 NumberOfCheckSat, 1106 ConstructedInterpolants, 135 QuantifiedInterpolants, 170584 SizeOfPredicates, 92 NumberOfNonLiveVariables, 11410 ConjunctsInSsa, 2300 ConjunctsInUnsatCore, 61 InterpolantComputations, 3 PerfectInterpolantSequences, 833/6564 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/019b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-30-11-380.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/019b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-30-11-380.csv Completed graceful shutdown