java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/xy10.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:47:59,052 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:47:59,054 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:47:59,068 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:47:59,069 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:47:59,069 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:47:59,071 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:47:59,075 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:47:59,077 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:47:59,077 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:47:59,078 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:47:59,078 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:47:59,079 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:47:59,081 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:47:59,082 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:47:59,083 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:47:59,084 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:47:59,086 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:47:59,087 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:47:59,088 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:47:59,089 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:47:59,092 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:47:59,092 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:47:59,092 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:47:59,093 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:47:59,150 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:47:59,151 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:47:59,152 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:47:59,153 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:47:59,153 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:47:59,154 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:47:59,154 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:47:59,155 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:47:59,155 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:47:59,156 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:47:59,156 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:47:59,181 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:47:59,182 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:47:59,182 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:47:59,182 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:47:59,184 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:47:59,184 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:47:59,185 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:47:59,185 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:47:59,185 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:47:59,185 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:47:59,186 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:47:59,186 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:47:59,186 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:47:59,186 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:47:59,186 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:47:59,186 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:47:59,187 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:47:59,187 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:47:59,187 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:47:59,189 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:47:59,189 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:47:59,228 INFO ]: Repository-Root is: /tmp [2018-06-22 15:47:59,247 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:47:59,252 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:47:59,254 INFO ]: Initializing SmtParser... [2018-06-22 15:47:59,254 INFO ]: SmtParser initialized [2018-06-22 15:47:59,255 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/xy10.c.smt2 [2018-06-22 15:47:59,256 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:47:59,355 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/xy10.c.smt2 unknown [2018-06-22 15:47:59,585 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/xy10.c.smt2 [2018-06-22 15:47:59,589 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:47:59,598 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:47:59,599 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:47:59,599 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:47:59,599 INFO ]: ChcToBoogie initialized [2018-06-22 15:47:59,606 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,652 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59 Unit [2018-06-22 15:47:59,652 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:47:59,653 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:47:59,653 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:47:59,653 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:47:59,675 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,675 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,682 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,683 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,686 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,688 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,689 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... [2018-06-22 15:47:59,690 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:47:59,698 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:47:59,698 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:47:59,698 INFO ]: RCFGBuilder initialized [2018-06-22 15:47:59,699 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 15:47:59,714 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:47:59,714 INFO ]: Found specification of procedure False [2018-06-22 15:47:59,714 INFO ]: Found implementation of procedure False [2018-06-22 15:47:59,714 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:47:59,714 INFO ]: Found specification of procedure state [2018-06-22 15:47:59,714 INFO ]: Found implementation of procedure state [2018-06-22 15:47:59,714 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:47:59,714 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:47:59,715 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:47:59,930 INFO ]: Using library mode [2018-06-22 15:47:59,931 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:47:59 BoogieIcfgContainer [2018-06-22 15:47:59,931 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:47:59,932 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:47:59,932 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:47:59,935 INFO ]: TraceAbstraction initialized [2018-06-22 15:47:59,935 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:47:59" (1/3) ... [2018-06-22 15:47:59,936 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@d7dcf19 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:47:59, skipping insertion in model container [2018-06-22 15:47:59,936 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:47:59" (2/3) ... [2018-06-22 15:47:59,937 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@d7dcf19 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:47:59, skipping insertion in model container [2018-06-22 15:47:59,937 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:47:59" (3/3) ... [2018-06-22 15:47:59,939 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:47:59,947 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:47:59,960 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:48:00,000 INFO ]: Using default assertion order modulation [2018-06-22 15:48:00,000 INFO ]: Interprodecural is true [2018-06-22 15:48:00,000 INFO ]: Hoare is false [2018-06-22 15:48:00,000 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:48:00,000 INFO ]: Backedges is TWOTRACK [2018-06-22 15:48:00,000 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:48:00,000 INFO ]: Difference is false [2018-06-22 15:48:00,000 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:48:00,000 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:48:00,013 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:48:00,026 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:48:00,026 INFO ]: Found error trace [2018-06-22 15:48:00,027 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:00,027 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:00,033 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:48:00,035 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:00,035 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:00,067 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:00,067 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:48:00,067 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:00,091 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:00,187 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:48:00,189 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:48:00,189 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:48:00,190 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:48:00,200 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:48:00,201 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:48:00,202 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:48:00,269 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:00,269 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:48:00,270 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:48:00,271 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:48:00,271 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:00,281 INFO ]: With dead ends: 13 [2018-06-22 15:48:00,281 INFO ]: Without dead ends: 13 [2018-06-22 15:48:00,283 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:48:00,297 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:48:00,319 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:48:00,320 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:48:00,321 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:48:00,322 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:48:00,322 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:00,322 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:48:00,322 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:48:00,322 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:48:00,325 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:48:00,325 INFO ]: Found error trace [2018-06-22 15:48:00,325 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:00,325 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:00,325 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:48:00,325 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:00,325 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:00,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:00,326 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:48:00,326 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:00,358 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:00,578 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:48:00,578 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:00,578 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 15:48:00,584 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:48:00,617 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:00,627 INFO ]: Computing forward predicates... [2018-06-22 15:48:00,811 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:48:00,833 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:00,833 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:48:00,833 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:48:00,834 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:48:00,834 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:48:00,834 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:48:00,934 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:00,934 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:48:00,935 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:48:00,935 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:48:00,935 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:00,936 INFO ]: With dead ends: 15 [2018-06-22 15:48:00,936 INFO ]: Without dead ends: 15 [2018-06-22 15:48:00,937 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:48:00,937 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:48:00,940 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:48:00,941 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:48:00,941 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:48:00,941 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:48:00,941 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:00,941 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:48:00,941 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:48:00,941 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:48:00,942 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:48:00,942 INFO ]: Found error trace [2018-06-22 15:48:00,942 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:00,942 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:00,942 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:48:00,942 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:00,942 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:00,945 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:00,945 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:48:00,945 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:01,005 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:01,389 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:48:01,389 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:01,389 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:01,395 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:48:01,436 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:48:01,436 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:01,439 INFO ]: Computing forward predicates... [2018-06-22 15:48:01,671 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:48:01,691 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:01,691 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:48:01,691 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:48:01,691 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:48:01,691 INFO ]: CoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:48:01,692 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:48:01,951 WARN ]: Spent 126.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 15:48:02,398 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:02,399 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:48:02,401 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:48:02,401 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:48:02,401 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:02,401 INFO ]: With dead ends: 17 [2018-06-22 15:48:02,401 INFO ]: Without dead ends: 17 [2018-06-22 15:48:02,402 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=49, Invalid=107, Unknown=0, NotChecked=0, Total=156 [2018-06-22 15:48:02,402 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:48:02,407 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:48:02,407 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:48:02,408 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:48:02,408 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:48:02,408 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:02,408 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:48:02,408 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:48:02,408 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:48:02,408 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:48:02,408 INFO ]: Found error trace [2018-06-22 15:48:02,409 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:02,409 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:02,409 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:48:02,409 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:02,409 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:02,410 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:02,410 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:02,410 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:02,447 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:02,782 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:48:02,782 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:02,782 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:02,813 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:48:02,890 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:48:02,890 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:02,895 INFO ]: Computing forward predicates... [2018-06-22 15:48:03,201 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 18 [2018-06-22 15:48:03,791 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:48:03,814 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:03,814 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 17 [2018-06-22 15:48:03,814 INFO ]: Interpolant automaton has 17 states [2018-06-22 15:48:03,815 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 15:48:03,815 INFO ]: CoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:48:03,815 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 17 states. [2018-06-22 15:48:04,349 WARN ]: Spent 477.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 40 [2018-06-22 15:48:04,557 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 37 [2018-06-22 15:48:04,658 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:04,658 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:48:04,660 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:48:04,660 INFO ]: Start accepts. Automaton has 17 states. Word has length 21 [2018-06-22 15:48:04,660 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:04,660 INFO ]: With dead ends: 19 [2018-06-22 15:48:04,660 INFO ]: Without dead ends: 19 [2018-06-22 15:48:04,661 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2018-06-22 15:48:04,661 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:48:04,664 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:48:04,664 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:48:04,665 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:48:04,665 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:48:04,665 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:04,665 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:48:04,665 INFO ]: Interpolant automaton has 17 states. [2018-06-22 15:48:04,665 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:48:04,666 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:48:04,666 INFO ]: Found error trace [2018-06-22 15:48:04,666 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:04,666 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:04,666 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:48:04,666 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:04,666 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:04,667 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:04,667 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:04,667 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:04,702 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:05,170 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:48:05,170 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:05,170 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:05,181 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:48:05,200 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:48:05,200 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:05,203 INFO ]: Computing forward predicates... [2018-06-22 15:48:05,666 WARN ]: Spent 316.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 27 [2018-06-22 15:48:05,885 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:48:05,905 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:05,905 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2018-06-22 15:48:05,905 INFO ]: Interpolant automaton has 20 states [2018-06-22 15:48:05,905 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 15:48:05,905 INFO ]: CoverageRelationStatistics Valid=49, Invalid=331, Unknown=0, NotChecked=0, Total=380 [2018-06-22 15:48:05,905 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-22 15:48:06,128 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 47 [2018-06-22 15:48:06,268 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 21 [2018-06-22 15:48:06,443 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 32 [2018-06-22 15:48:06,598 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 24 [2018-06-22 15:48:06,791 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 25 [2018-06-22 15:48:06,831 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:06,831 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:48:06,832 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:48:06,832 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-22 15:48:06,832 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:06,833 INFO ]: With dead ends: 21 [2018-06-22 15:48:06,833 INFO ]: Without dead ends: 21 [2018-06-22 15:48:06,833 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=116, Invalid=534, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:48:06,834 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:48:06,836 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:48:06,836 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:48:06,837 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:48:06,837 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:48:06,837 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:06,837 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:48:06,837 INFO ]: Interpolant automaton has 20 states. [2018-06-22 15:48:06,837 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:48:06,838 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:48:06,838 INFO ]: Found error trace [2018-06-22 15:48:06,838 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:06,839 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:06,839 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:48:06,839 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:06,839 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:06,839 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:06,839 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:06,839 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:06,874 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:07,199 WARN ]: Spent 164.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 15:48:07,392 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:48:07,392 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:07,392 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:07,398 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:48:07,426 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:48:07,426 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:07,430 INFO ]: Computing forward predicates... [2018-06-22 15:48:07,673 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 27 [2018-06-22 15:48:07,929 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:48:07,949 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:07,949 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 15:48:07,949 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:48:07,949 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:48:07,950 INFO ]: CoverageRelationStatistics Valid=56, Invalid=286, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:48:07,950 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 15:48:08,137 WARN ]: Spent 167.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 49 [2018-06-22 15:48:08,300 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 21 [2018-06-22 15:48:08,752 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 26 [2018-06-22 15:48:09,137 WARN ]: Spent 358.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 38 [2018-06-22 15:48:09,236 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:09,236 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:48:09,236 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:48:09,237 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 15:48:09,237 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:09,237 INFO ]: With dead ends: 23 [2018-06-22 15:48:09,237 INFO ]: Without dead ends: 23 [2018-06-22 15:48:09,238 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=134, Invalid=466, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:48:09,238 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:48:09,241 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:48:09,241 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:48:09,242 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:48:09,242 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:48:09,242 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:09,242 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:48:09,242 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:48:09,242 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:48:09,243 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:48:09,243 INFO ]: Found error trace [2018-06-22 15:48:09,243 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:09,243 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:09,243 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:48:09,243 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:09,243 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:09,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:09,244 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:09,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:09,285 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:09,719 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:48:09,720 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:09,720 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 15:48:09,737 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:09,853 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:48:09,853 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:09,858 INFO ]: Computing forward predicates... [2018-06-22 15:48:10,059 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 9 [2018-06-22 15:48:10,756 WARN ]: Spent 260.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 32 [2018-06-22 15:48:12,166 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:48:12,198 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:12,199 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-06-22 15:48:12,199 INFO ]: Interpolant automaton has 25 states [2018-06-22 15:48:12,199 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 15:48:12,199 INFO ]: CoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2018-06-22 15:48:12,200 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 25 states. [2018-06-22 15:48:13,068 WARN ]: Spent 564.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 53 [2018-06-22 15:48:13,264 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 23 [2018-06-22 15:48:13,445 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 33 [2018-06-22 15:48:13,633 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 27 [2018-06-22 15:48:13,844 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 26 [2018-06-22 15:48:14,043 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 28 [2018-06-22 15:48:14,417 WARN ]: Spent 352.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 46 [2018-06-22 15:48:14,448 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:14,448 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:48:14,449 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:48:14,449 INFO ]: Start accepts. Automaton has 25 states. Word has length 33 [2018-06-22 15:48:14,449 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:14,450 INFO ]: With dead ends: 25 [2018-06-22 15:48:14,450 INFO ]: Without dead ends: 25 [2018-06-22 15:48:14,450 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=212, Invalid=780, Unknown=0, NotChecked=0, Total=992 [2018-06-22 15:48:14,450 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:48:14,454 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:48:14,454 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:48:14,455 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:48:14,455 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:48:14,455 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:14,455 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:48:14,455 INFO ]: Interpolant automaton has 25 states. [2018-06-22 15:48:14,455 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:48:14,456 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:48:14,456 INFO ]: Found error trace [2018-06-22 15:48:14,456 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:14,456 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:14,456 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:48:14,456 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:14,456 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:14,457 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:14,457 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:14,457 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:14,519 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:15,300 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:48:15,300 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:15,300 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:15,316 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:48:15,347 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:15,353 INFO ]: Computing forward predicates... [2018-06-22 15:48:15,919 WARN ]: Spent 485.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 36 [2018-06-22 15:48:17,585 WARN ]: Spent 1.37 s on a formula simplification. DAG size of input: 131 DAG size of output: 79 [2018-06-22 15:48:17,806 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 33 [2018-06-22 15:48:17,996 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 38 [2018-06-22 15:48:18,229 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 34 [2018-06-22 15:48:22,602 INFO ]: Checked inductivity of 105 backedges. 1 proven. 76 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:48:22,621 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:22,621 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 32 [2018-06-22 15:48:22,622 INFO ]: Interpolant automaton has 32 states [2018-06-22 15:48:22,622 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 15:48:22,622 INFO ]: CoverageRelationStatistics Valid=104, Invalid=888, Unknown=0, NotChecked=0, Total=992 [2018-06-22 15:48:22,622 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 32 states. [2018-06-22 15:48:24,018 WARN ]: Spent 1.30 s on a formula simplification. DAG size of input: 137 DAG size of output: 100 [2018-06-22 15:48:24,533 WARN ]: Spent 421.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 30 [2018-06-22 15:48:24,899 WARN ]: Spent 306.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 29 [2018-06-22 15:48:25,329 WARN ]: Spent 375.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 41 [2018-06-22 15:48:25,908 WARN ]: Spent 534.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 41 [2018-06-22 15:48:26,373 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 41 [2018-06-22 15:48:27,130 WARN ]: Spent 687.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 45 [2018-06-22 15:48:28,058 WARN ]: Spent 852.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 84 [2018-06-22 15:48:28,133 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:28,133 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 15:48:28,133 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 15:48:28,133 INFO ]: Start accepts. Automaton has 32 states. Word has length 37 [2018-06-22 15:48:28,134 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:28,134 INFO ]: With dead ends: 27 [2018-06-22 15:48:28,134 INFO ]: Without dead ends: 27 [2018-06-22 15:48:28,135 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 207 ImplicationChecksByTransitivity, 9.5s TimeCoverageRelationStatistics Valid=264, Invalid=1376, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:48:28,135 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 15:48:28,138 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 15:48:28,138 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 15:48:28,139 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 15:48:28,139 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 15:48:28,139 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:28,139 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 15:48:28,139 INFO ]: Interpolant automaton has 32 states. [2018-06-22 15:48:28,139 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 15:48:28,140 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 15:48:28,140 INFO ]: Found error trace [2018-06-22 15:48:28,140 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:28,141 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:28,141 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-22 15:48:28,141 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:28,141 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:28,141 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:28,141 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:48:28,141 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:28,205 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:29,057 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:48:29,057 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:29,057 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:29,063 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:48:29,098 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:48:29,098 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:29,104 INFO ]: Computing forward predicates... [2018-06-22 15:48:29,476 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 32 [2018-06-22 15:48:30,004 WARN ]: Spent 456.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 52 [2018-06-22 15:48:30,297 WARN ]: Spent 247.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 33 [2018-06-22 15:48:30,510 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 33 [2018-06-22 15:48:30,660 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 38 [2018-06-22 15:48:31,259 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 34 [2018-06-22 15:48:33,297 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-22 15:48:33,317 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:33,317 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 36 [2018-06-22 15:48:33,317 INFO ]: Interpolant automaton has 36 states [2018-06-22 15:48:33,317 INFO ]: Constructing interpolant automaton starting with 36 interpolants. [2018-06-22 15:48:33,318 INFO ]: CoverageRelationStatistics Valid=120, Invalid=1140, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 15:48:33,318 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 36 states. [2018-06-22 15:48:33,938 WARN ]: Spent 571.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 70 [2018-06-22 15:48:34,218 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 126 DAG size of output: 29 [2018-06-22 15:48:34,669 WARN ]: Spent 355.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 32 [2018-06-22 15:48:35,131 WARN ]: Spent 398.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 40 [2018-06-22 15:48:35,530 WARN ]: Spent 280.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 45 [2018-06-22 15:48:35,877 WARN ]: Spent 305.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 43 [2018-06-22 15:48:36,270 WARN ]: Spent 344.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 42 [2018-06-22 15:48:36,760 WARN ]: Spent 447.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 50 [2018-06-22 15:48:37,364 WARN ]: Spent 548.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 70 [2018-06-22 15:48:37,405 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:37,405 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 15:48:37,406 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 15:48:37,406 INFO ]: Start accepts. Automaton has 36 states. Word has length 41 [2018-06-22 15:48:37,406 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:37,406 INFO ]: With dead ends: 29 [2018-06-22 15:48:37,406 INFO ]: Without dead ends: 29 [2018-06-22 15:48:37,407 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 262 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=319, Invalid=1661, Unknown=0, NotChecked=0, Total=1980 [2018-06-22 15:48:37,407 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 15:48:37,410 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 15:48:37,410 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 15:48:37,411 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 15:48:37,411 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-22 15:48:37,411 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:37,411 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 15:48:37,411 INFO ]: Interpolant automaton has 36 states. [2018-06-22 15:48:37,411 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 15:48:37,412 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 15:48:37,412 INFO ]: Found error trace [2018-06-22 15:48:37,412 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:37,412 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:37,412 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-22 15:48:37,412 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:37,412 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:37,413 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:37,413 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:37,413 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:37,491 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:38,487 WARN ]: Spent 802.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 12 [2018-06-22 15:48:38,755 WARN ]: Spent 189.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 15:48:39,107 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 45 [2018-06-22 15:48:39,740 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:48:39,740 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:39,740 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:39,746 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:48:39,792 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-22 15:48:39,792 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:39,800 INFO ]: Computing forward predicates... [2018-06-22 15:48:39,978 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 20 [2018-06-22 15:48:40,153 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 31 [2018-06-22 15:48:40,304 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 27 [2018-06-22 15:48:41,697 WARN ]: Spent 1.29 s on a formula simplification. DAG size of input: 98 DAG size of output: 71 [2018-06-22 15:48:41,851 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 38 [2018-06-22 15:48:42,033 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 34 [2018-06-22 15:48:45,632 INFO ]: Checked inductivity of 171 backedges. 1 proven. 125 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 15:48:45,652 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:45,652 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-06-22 15:48:45,652 INFO ]: Interpolant automaton has 35 states [2018-06-22 15:48:45,652 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 15:48:45,653 INFO ]: CoverageRelationStatistics Valid=132, Invalid=1058, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:48:45,653 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 35 states. [2018-06-22 15:48:46,404 WARN ]: Spent 672.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 81 [2018-06-22 15:48:46,808 WARN ]: Spent 343.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 32 [2018-06-22 15:48:47,131 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 32 [2018-06-22 15:48:47,441 WARN ]: Spent 274.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 41 [2018-06-22 15:48:47,842 WARN ]: Spent 362.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 42 [2018-06-22 15:48:48,308 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 41 [2018-06-22 15:48:48,950 WARN ]: Spent 590.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 44 [2018-06-22 15:48:49,352 WARN ]: Spent 363.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 41 [2018-06-22 15:48:49,828 WARN ]: Spent 435.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 40 [2018-06-22 15:48:50,395 WARN ]: Spent 509.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 63 [2018-06-22 15:48:50,439 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:50,439 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 15:48:50,439 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 15:48:50,439 INFO ]: Start accepts. Automaton has 35 states. Word has length 45 [2018-06-22 15:48:50,440 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:50,440 INFO ]: With dead ends: 31 [2018-06-22 15:48:50,440 INFO ]: Without dead ends: 31 [2018-06-22 15:48:50,441 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 324 ImplicationChecksByTransitivity, 9.1s TimeCoverageRelationStatistics Valid=352, Invalid=1628, Unknown=0, NotChecked=0, Total=1980 [2018-06-22 15:48:50,441 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 15:48:50,444 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 15:48:50,444 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 15:48:50,445 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 15:48:50,445 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 15:48:50,445 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:50,445 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 15:48:50,445 INFO ]: Interpolant automaton has 35 states. [2018-06-22 15:48:50,445 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 15:48:50,446 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 15:48:50,446 INFO ]: Found error trace [2018-06-22 15:48:50,446 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:50,446 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:50,446 INFO ]: Analyzing trace with hash 352352522, now seen corresponding path program 10 times [2018-06-22 15:48:50,446 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:50,446 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:50,447 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:50,447 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:50,447 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:50,551 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:51,262 WARN ]: Spent 468.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 11 [2018-06-22 15:48:52,657 INFO ]: Checked inductivity of 210 backedges. 1 proven. 154 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:48:52,657 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:48:52,657 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:48:52,663 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:48:52,703 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:48:52,703 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:48:52,712 INFO ]: Computing forward predicates... [2018-06-22 15:48:53,089 WARN ]: Spent 272.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 10 [2018-06-22 15:48:53,335 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 31 [2018-06-22 15:48:53,652 WARN ]: Spent 260.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 35 [2018-06-22 15:48:53,924 WARN ]: Spent 224.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 32 [2018-06-22 15:48:54,197 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 27 [2018-06-22 15:48:54,647 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 34 [2018-06-22 15:48:55,348 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-22 15:48:55,368 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:48:55,368 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 41 [2018-06-22 15:48:55,368 INFO ]: Interpolant automaton has 41 states [2018-06-22 15:48:55,368 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 15:48:55,369 INFO ]: CoverageRelationStatistics Valid=164, Invalid=1476, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 15:48:55,369 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 41 states. [2018-06-22 15:48:55,983 WARN ]: Spent 567.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 77 [2018-06-22 15:48:56,304 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 33 [2018-06-22 15:48:56,508 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 112 DAG size of output: 33 [2018-06-22 15:48:57,012 WARN ]: Spent 460.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 39 [2018-06-22 15:48:57,301 WARN ]: Spent 248.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 44 [2018-06-22 15:48:57,653 WARN ]: Spent 313.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 42 [2018-06-22 15:48:58,119 WARN ]: Spent 339.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 43 [2018-06-22 15:48:58,430 WARN ]: Spent 270.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 43 [2018-06-22 15:48:58,783 WARN ]: Spent 316.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 44 [2018-06-22 15:48:59,177 WARN ]: Spent 345.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 48 [2018-06-22 15:48:59,731 WARN ]: Spent 505.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 72 [2018-06-22 15:48:59,772 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:48:59,772 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-22 15:48:59,773 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 15:48:59,773 INFO ]: Start accepts. Automaton has 41 states. Word has length 49 [2018-06-22 15:48:59,774 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:48:59,774 INFO ]: With dead ends: 33 [2018-06-22 15:48:59,774 INFO ]: Without dead ends: 33 [2018-06-22 15:48:59,775 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 498 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=451, Invalid=2201, Unknown=0, NotChecked=0, Total=2652 [2018-06-22 15:48:59,775 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-22 15:48:59,780 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-22 15:48:59,780 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-22 15:48:59,781 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-22 15:48:59,781 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 49 [2018-06-22 15:48:59,781 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:48:59,781 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-22 15:48:59,781 INFO ]: Interpolant automaton has 41 states. [2018-06-22 15:48:59,781 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-22 15:48:59,782 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 15:48:59,782 INFO ]: Found error trace [2018-06-22 15:48:59,782 INFO ]: trace histogram [12, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:48:59,782 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:48:59,782 INFO ]: Analyzing trace with hash 53554094, now seen corresponding path program 11 times [2018-06-22 15:48:59,782 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:48:59,782 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:48:59,783 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:59,783 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:48:59,783 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:48:59,858 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:49:00,383 WARN ]: Spent 250.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 15:49:00,724 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 35 [2018-06-22 15:49:00,961 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 47 [2018-06-22 15:49:01,545 INFO ]: Checked inductivity of 253 backedges. 4 proven. 183 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-22 15:49:01,545 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:49:01,545 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 15:49:01,552 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:49:01,608 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 15:49:01,608 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:49:01,615 INFO ]: Computing forward predicates... [2018-06-22 15:49:02,077 WARN ]: Spent 369.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 34 Received shutdown request... [2018-06-22 15:49:02,417 WARN ]: Removed 9 from assertion stack [2018-06-22 15:49:02,417 INFO ]: Timeout while computing interpolants [2018-06-22 15:49:02,618 WARN ]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:49:02,618 WARN ]: Verification canceled [2018-06-22 15:49:02,622 WARN ]: Timeout [2018-06-22 15:49:02,622 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:49:02 BoogieIcfgContainer [2018-06-22 15:49:02,622 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:49:02,623 INFO ]: Toolchain (without parser) took 63033.08 ms. Allocated memory was 303.0 MB in the beginning and 950.5 MB in the end (delta: 647.5 MB). Free memory was 258.4 MB in the beginning and 838.1 MB in the end (delta: -579.7 MB). Peak memory consumption was 742.6 MB. Max. memory is 3.6 GB. [2018-06-22 15:49:02,623 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 303.0 MB. Free memory is still 268.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:49:02,624 INFO ]: ChcToBoogie took 53.67 ms. Allocated memory is still 303.0 MB. Free memory was 257.4 MB in the beginning and 256.4 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-22 15:49:02,624 INFO ]: Boogie Preprocessor took 37.53 ms. Allocated memory is still 303.0 MB. Free memory was 256.4 MB in the beginning and 254.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:49:02,625 INFO ]: RCFGBuilder took 233.53 ms. Allocated memory is still 303.0 MB. Free memory was 254.4 MB in the beginning and 246.4 MB in the end (delta: 8.1 MB). Peak memory consumption was 8.1 MB. Max. memory is 3.6 GB. [2018-06-22 15:49:02,625 INFO ]: TraceAbstraction took 62689.92 ms. Allocated memory was 303.0 MB in the beginning and 950.5 MB in the end (delta: 647.5 MB). Free memory was 246.4 MB in the beginning and 838.1 MB in the end (delta: -591.7 MB). Peak memory consumption was 730.5 MB. Max. memory is 3.6 GB. [2018-06-22 15:49:02,628 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 303.0 MB. Free memory is still 268.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 53.67 ms. Allocated memory is still 303.0 MB. Free memory was 257.4 MB in the beginning and 256.4 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * Boogie Preprocessor took 37.53 ms. Allocated memory is still 303.0 MB. Free memory was 256.4 MB in the beginning and 254.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 233.53 ms. Allocated memory is still 303.0 MB. Free memory was 254.4 MB in the beginning and 246.4 MB in the end (delta: 8.1 MB). Peak memory consumption was 8.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62689.92 ms. Allocated memory was 303.0 MB in the beginning and 950.5 MB in the end (delta: 647.5 MB). Free memory was 246.4 MB in the beginning and 838.1 MB in the end (delta: -591.7 MB). Peak memory consumption was 730.5 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 54 with TraceHistMax 12, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 53. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 62.6s OverallTime, 12 OverallIterations, 12 TraceHistogramMax, 25.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 152 SDtfs, 646 SDslu, 1255 SDs, 0 SdLazy, 1112 SolverSat, 757 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 519 GetRequests, 221 SyntacticMatches, 9 SemanticMatches, 289 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1618 ImplicationChecksByTransitivity, 43.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=33occurred in iteration=11, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 11 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 33.1s InterpolantComputationTime, 629 NumberOfCodeBlocks, 629 NumberOfCodeBlocksAsserted, 46 NumberOfCheckSat, 608 ConstructedInterpolants, 0 QuantifiedInterpolants, 5737212 SizeOfPredicates, 523 NumberOfNonLiveVariables, 1730 ConjunctsInSsa, 530 ConjunctsInUnsatCore, 21 InterpolantComputations, 1 PerfectInterpolantSequences, 443/1650 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/xy10.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-49-02-639.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/xy10.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-49-02-639.csv Completed graceful shutdown