java -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/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/substring1.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 13:43:48,293 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 13:43:48,296 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 13:43:48,311 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 13:43:48,312 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 13:43:48,313 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 13:43:48,315 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 13:43:48,317 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 13:43:48,318 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 13:43:48,320 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 13:43:48,321 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 13:43:48,321 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 13:43:48,322 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 13:43:48,323 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 13:43:48,323 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 13:43:48,327 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 13:43:48,329 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 13:43:48,342 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 13:43:48,344 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 13:43:48,345 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 13:43:48,346 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 13:43:48,348 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 13:43:48,348 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 13:43:48,348 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 13:43:48,349 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 13:43:48,356 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 13:43:48,357 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 13:43:48,358 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 13:43:48,359 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 13:43:48,359 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 13:43:48,360 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 13:43:48,360 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 13:43:48,360 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 13:43:48,361 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 13:43:48,362 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 13:43:48,362 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 13:43:48,388 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 13:43:48,388 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 13:43:48,388 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 13:43:48,388 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 13:43:48,390 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 13:43:48,391 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 13:43:48,391 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 13:43:48,391 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 13:43:48,391 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:43:48,391 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 13:43:48,392 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 13:43:48,392 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 13:43:48,392 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 13:43:48,392 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 13:43:48,392 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 13:43:48,392 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 13:43:48,393 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 13:43:48,397 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 13:43:48,398 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 13:43:48,445 INFO ]: Repository-Root is: /tmp [2018-06-18 13:43:48,462 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 13:43:48,467 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 13:43:48,469 INFO ]: Initializing SmtParser... [2018-06-18 13:43:48,469 INFO ]: SmtParser initialized [2018-06-18 13:43:48,470 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/substring1.c.smt2 [2018-06-18 13:43:48,471 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-18 13:43:48,559 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/substring1.c.smt2 unknown [2018-06-18 13:43:48,840 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/substring1.c.smt2 [2018-06-18 13:43:48,845 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 13:43:48,850 INFO ]: Walking toolchain with 4 elements. [2018-06-18 13:43:48,850 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 13:43:48,850 INFO ]: Initializing ChcToBoogie... [2018-06-18 13:43:48,850 INFO ]: ChcToBoogie initialized [2018-06-18 13:43:48,857 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,925 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48 Unit [2018-06-18 13:43:48,925 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 13:43:48,926 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 13:43:48,926 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 13:43:48,926 INFO ]: Boogie Preprocessor initialized [2018-06-18 13:43:48,948 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,948 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,959 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,959 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,976 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,977 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,979 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (1/1) ... [2018-06-18 13:43:48,981 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 13:43:48,982 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 13:43:48,982 INFO ]: Initializing RCFGBuilder... [2018-06-18 13:43:48,991 INFO ]: RCFGBuilder initialized [2018-06-18 13:43:48,992 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (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-18 13:43:49,014 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 13:43:49,014 INFO ]: Found specification of procedure False [2018-06-18 13:43:49,014 INFO ]: Found implementation of procedure False [2018-06-18 13:43:49,014 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 13:43:49,014 INFO ]: Found specification of procedure state [2018-06-18 13:43:49,014 INFO ]: Found implementation of procedure state [2018-06-18 13:43:49,014 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 13:43:49,014 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 13:43:49,014 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-18 13:43:49,246 INFO ]: Using library mode [2018-06-18 13:43:49,247 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:43:49 BoogieIcfgContainer [2018-06-18 13:43:49,247 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 13:43:49,248 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 13:43:49,248 INFO ]: Initializing TraceAbstraction... [2018-06-18 13:43:49,251 INFO ]: TraceAbstraction initialized [2018-06-18 13:43:49,252 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:43:48" (1/3) ... [2018-06-18 13:43:49,252 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@fcff240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 01:43:49, skipping insertion in model container [2018-06-18 13:43:49,253 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:43:48" (2/3) ... [2018-06-18 13:43:49,253 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@fcff240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 01:43:49, skipping insertion in model container [2018-06-18 13:43:49,253 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:43:49" (3/3) ... [2018-06-18 13:43:49,255 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 13:43:49,264 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 13:43:49,271 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 13:43:49,318 INFO ]: Using default assertion order modulation [2018-06-18 13:43:49,318 INFO ]: Interprodecural is true [2018-06-18 13:43:49,318 INFO ]: Hoare is false [2018-06-18 13:43:49,318 INFO ]: Compute interpolants for FPandBP [2018-06-18 13:43:49,318 INFO ]: Backedges is TWOTRACK [2018-06-18 13:43:49,318 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 13:43:49,318 INFO ]: Difference is false [2018-06-18 13:43:49,319 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 13:43:49,319 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 13:43:49,332 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 13:43:49,341 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 13:43:49,342 INFO ]: Found error trace [2018-06-18 13:43:49,342 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:43:49,343 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:43:49,347 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 13:43:49,349 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:43:49,349 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:43:49,385 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:49,385 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:43:49,385 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:49,414 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:49,421 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:43:49,507 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 13:43:49,510 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 13:43:49,510 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 13:43:49,512 INFO ]: Interpolant automaton has 4 states [2018-06-18 13:43:49,537 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 13:43:49,537 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:43:49,544 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 13:43:49,671 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:43:49,671 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 13:43:49,672 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 13:43:49,673 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 13:43:49,674 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:43:49,684 INFO ]: With dead ends: 13 [2018-06-18 13:43:49,684 INFO ]: Without dead ends: 13 [2018-06-18 13:43:49,686 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-18 13:43:49,704 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 13:43:49,727 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 13:43:49,729 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 13:43:49,729 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 13:43:49,730 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 13:43:49,730 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:43:49,731 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 13:43:49,731 INFO ]: Interpolant automaton has 4 states. [2018-06-18 13:43:49,731 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 13:43:49,732 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 13:43:49,732 INFO ]: Found error trace [2018-06-18 13:43:49,732 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:43:49,732 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:43:49,732 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 13:43:49,732 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:43:49,732 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:43:49,733 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:49,733 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:43:49,733 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:49,793 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:49,794 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:43:50,026 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:43:50,026 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:43:50,026 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-18 13:43:50,034 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:43:50,078 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:50,088 INFO ]: Computing forward predicates... [2018-06-18 13:43:50,478 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:43:50,505 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:43:50,506 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-18 13:43:50,506 INFO ]: Interpolant automaton has 6 states [2018-06-18 13:43:50,506 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-18 13:43:50,506 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-18 13:43:50,506 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-18 13:43:50,700 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:43:50,700 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 13:43:50,702 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 13:43:50,702 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-18 13:43:50,702 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:43:50,702 INFO ]: With dead ends: 15 [2018-06-18 13:43:50,702 INFO ]: Without dead ends: 15 [2018-06-18 13:43:50,703 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-18 13:43:50,703 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 13:43:50,708 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 13:43:50,708 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 13:43:50,709 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 13:43:50,709 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 13:43:50,709 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:43:50,709 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 13:43:50,709 INFO ]: Interpolant automaton has 6 states. [2018-06-18 13:43:50,709 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 13:43:50,710 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 13:43:50,710 INFO ]: Found error trace [2018-06-18 13:43:50,710 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:43:50,710 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:43:50,710 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 13:43:50,710 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:43:50,710 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:43:50,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:50,711 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:43:50,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:50,779 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:50,780 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:43:51,339 WARN ]: Spent 396.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-18 13:43:51,747 WARN ]: Spent 351.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 16 [2018-06-18 13:43:51,891 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:43:51,891 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:43:51,891 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-18 13:43:51,906 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:43:51,973 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:43:51,973 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:51,976 INFO ]: Computing forward predicates... [2018-06-18 13:43:52,543 WARN ]: Spent 366.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 8 [2018-06-18 13:43:52,811 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:43:52,839 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:43:52,839 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-18 13:43:52,839 INFO ]: Interpolant automaton has 11 states [2018-06-18 13:43:52,840 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-18 13:43:52,840 INFO ]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2018-06-18 13:43:52,840 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-18 13:43:53,168 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 19 [2018-06-18 13:43:53,207 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:43:53,207 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 13:43:53,209 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 13:43:53,209 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-18 13:43:53,209 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:43:53,210 INFO ]: With dead ends: 17 [2018-06-18 13:43:53,210 INFO ]: Without dead ends: 17 [2018-06-18 13:43:53,210 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=52, Invalid=130, Unknown=0, NotChecked=0, Total=182 [2018-06-18 13:43:53,211 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 13:43:53,213 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 13:43:53,213 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 13:43:53,214 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 13:43:53,214 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 13:43:53,214 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:43:53,214 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 13:43:53,214 INFO ]: Interpolant automaton has 11 states. [2018-06-18 13:43:53,215 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 13:43:53,215 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 13:43:53,215 INFO ]: Found error trace [2018-06-18 13:43:53,215 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:43:53,215 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:43:53,215 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-18 13:43:53,216 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:43:53,216 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:43:53,216 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:53,216 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:43:53,217 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:53,257 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:53,257 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:43:53,670 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:43:53,670 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:43:53,670 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-18 13:43:53,686 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 13:43:53,777 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 13:43:53,777 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:53,782 INFO ]: Computing forward predicates... [2018-06-18 13:43:54,243 WARN ]: Spent 242.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 13 [2018-06-18 13:43:54,674 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 22 [2018-06-18 13:43:54,755 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:43:54,779 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:43:54,779 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-18 13:43:54,779 INFO ]: Interpolant automaton has 14 states [2018-06-18 13:43:54,779 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-18 13:43:54,779 INFO ]: CoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2018-06-18 13:43:54,780 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 14 states. [2018-06-18 13:43:54,947 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 26 [2018-06-18 13:43:55,147 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 26 [2018-06-18 13:43:55,270 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:43:55,270 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 13:43:55,271 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 13:43:55,271 INFO ]: Start accepts. Automaton has 14 states. Word has length 21 [2018-06-18 13:43:55,271 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:43:55,272 INFO ]: With dead ends: 19 [2018-06-18 13:43:55,272 INFO ]: Without dead ends: 19 [2018-06-18 13:43:55,272 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=86, Invalid=220, Unknown=0, NotChecked=0, Total=306 [2018-06-18 13:43:55,272 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 13:43:55,275 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 13:43:55,275 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 13:43:55,276 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 13:43:55,276 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 13:43:55,276 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:43:55,276 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 13:43:55,276 INFO ]: Interpolant automaton has 14 states. [2018-06-18 13:43:55,276 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 13:43:55,277 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 13:43:55,277 INFO ]: Found error trace [2018-06-18 13:43:55,277 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:43:55,277 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:43:55,277 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-18 13:43:55,277 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:43:55,277 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:43:55,278 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:55,278 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:43:55,278 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:43:55,320 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:55,321 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:43:55,766 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:43:55,766 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:43:55,766 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-18 13:43:55,772 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:43:55,816 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:43:55,816 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:43:55,820 INFO ]: Computing forward predicates... [2018-06-18 13:44:05,951 WARN ]: Spent 8.17 s on a formula simplification. DAG size of input: 789 DAG size of output: 6 [2018-06-18 13:44:06,301 WARN ]: Spent 135.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 22 [2018-06-18 13:44:07,911 WARN ]: Spent 372.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-18 13:44:08,190 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:44:08,224 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:08,224 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-18 13:44:08,224 INFO ]: Interpolant automaton has 17 states [2018-06-18 13:44:08,224 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-18 13:44:08,224 INFO ]: CoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2018-06-18 13:44:08,224 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 17 states. [2018-06-18 13:44:08,603 WARN ]: Spent 233.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 34 [2018-06-18 13:44:08,932 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 25 [2018-06-18 13:44:09,061 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:44:09,062 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 13:44:09,062 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 13:44:09,062 INFO ]: Start accepts. Automaton has 17 states. Word has length 25 [2018-06-18 13:44:09,062 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:44:09,063 INFO ]: With dead ends: 21 [2018-06-18 13:44:09,063 INFO ]: Without dead ends: 21 [2018-06-18 13:44:09,063 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 18 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 11.4s TimeCoverageRelationStatistics Valid=118, Invalid=344, Unknown=0, NotChecked=0, Total=462 [2018-06-18 13:44:09,063 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 13:44:09,066 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 13:44:09,066 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 13:44:09,068 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 13:44:09,069 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 13:44:09,069 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:44:09,069 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 13:44:09,069 INFO ]: Interpolant automaton has 17 states. [2018-06-18 13:44:09,069 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 13:44:09,070 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 13:44:09,070 INFO ]: Found error trace [2018-06-18 13:44:09,070 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:44:09,070 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:44:09,070 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-18 13:44:09,070 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:44:09,070 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:44:09,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:09,071 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:44:09,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:09,148 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:09,149 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:44:09,527 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2018-06-18 13:44:09,773 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 24 [2018-06-18 13:44:09,906 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 22 [2018-06-18 13:44:10,059 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 31 [2018-06-18 13:44:10,364 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 24 [2018-06-18 13:44:10,564 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:44:10,564 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:44:10,564 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-18 13:44:10,575 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 13:44:10,684 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-18 13:44:10,685 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:10,693 INFO ]: Computing forward predicates... [2018-06-18 13:44:11,411 WARN ]: Spent 300.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 29 [2018-06-18 13:44:11,868 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 22 [2018-06-18 13:44:12,194 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 22 [2018-06-18 13:44:12,440 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:44:12,459 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:12,460 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 22 [2018-06-18 13:44:12,460 INFO ]: Interpolant automaton has 22 states [2018-06-18 13:44:12,460 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-18 13:44:12,460 INFO ]: CoverageRelationStatistics Valid=76, Invalid=386, Unknown=0, NotChecked=0, Total=462 [2018-06-18 13:44:12,461 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 22 states. [2018-06-18 13:44:12,709 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 42 [2018-06-18 13:44:13,069 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 27 [2018-06-18 13:44:13,341 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-06-18 13:44:13,373 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:44:13,373 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 13:44:13,377 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:44:13,377 INFO ]: Start accepts. Automaton has 22 states. Word has length 29 [2018-06-18 13:44:13,377 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:44:13,378 INFO ]: With dead ends: 23 [2018-06-18 13:44:13,378 INFO ]: Without dead ends: 23 [2018-06-18 13:44:13,379 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=172, Invalid=584, Unknown=0, NotChecked=0, Total=756 [2018-06-18 13:44:13,379 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 13:44:13,384 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 13:44:13,384 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 13:44:13,384 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 13:44:13,384 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 13:44:13,385 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:44:13,385 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 13:44:13,385 INFO ]: Interpolant automaton has 22 states. [2018-06-18 13:44:13,385 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 13:44:13,385 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 13:44:13,386 INFO ]: Found error trace [2018-06-18 13:44:13,386 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:44:13,388 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:44:13,388 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-18 13:44:13,388 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:44:13,388 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:44:13,389 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:13,389 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:44:13,389 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:13,472 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:13,473 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:44:14,110 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:44:14,110 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:44:14,110 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-18 13:44:14,116 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-18 13:44:14,187 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-18 13:44:14,187 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:14,192 INFO ]: Computing forward predicates... [2018-06-18 13:44:14,684 WARN ]: Spent 282.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 5 [2018-06-18 13:44:15,081 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 23 [2018-06-18 13:44:15,307 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 29 [2018-06-18 13:44:15,464 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 22 [2018-06-18 13:44:15,737 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 22 [2018-06-18 13:44:15,894 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:44:15,924 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:15,925 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 23 [2018-06-18 13:44:15,925 INFO ]: Interpolant automaton has 23 states [2018-06-18 13:44:15,925 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-18 13:44:15,925 INFO ]: CoverageRelationStatistics Valid=70, Invalid=436, Unknown=0, NotChecked=0, Total=506 [2018-06-18 13:44:15,925 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 23 states. [2018-06-18 13:44:16,123 WARN ]: Spent 174.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 42 [2018-06-18 13:44:16,472 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 30 [2018-06-18 13:44:16,653 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 30 [2018-06-18 13:44:16,844 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 31 [2018-06-18 13:44:17,017 WARN ]: Spent 119.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 29 [2018-06-18 13:44:17,219 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 41 [2018-06-18 13:44:17,246 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:44:17,246 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 13:44:17,248 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 13:44:17,248 INFO ]: Start accepts. Automaton has 23 states. Word has length 33 [2018-06-18 13:44:17,248 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:44:17,249 INFO ]: With dead ends: 25 [2018-06-18 13:44:17,249 INFO ]: Without dead ends: 25 [2018-06-18 13:44:17,249 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 24 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=189, Invalid=681, Unknown=0, NotChecked=0, Total=870 [2018-06-18 13:44:17,250 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 13:44:17,253 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 13:44:17,253 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 13:44:17,254 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 13:44:17,254 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 13:44:17,254 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:44:17,254 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 13:44:17,254 INFO ]: Interpolant automaton has 23 states. [2018-06-18 13:44:17,254 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 13:44:17,255 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 13:44:17,255 INFO ]: Found error trace [2018-06-18 13:44:17,255 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:44:17,255 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:44:17,255 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-18 13:44:17,255 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:44:17,255 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:44:17,256 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:17,256 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:44:17,256 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:17,329 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:17,329 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:44:18,068 WARN ]: Spent 508.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-18 13:44:18,290 WARN ]: Spent 151.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2018-06-18 13:44:18,574 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 28 [2018-06-18 13:44:18,730 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 23 [2018-06-18 13:44:19,037 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-18 13:44:19,037 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:44:19,037 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-18 13:44:19,044 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:44:19,109 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:19,114 INFO ]: Computing forward predicates... [2018-06-18 13:44:19,471 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 23 [2018-06-18 13:44:19,688 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 29 [2018-06-18 13:44:19,845 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 22 [2018-06-18 13:44:20,315 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-18 13:44:20,337 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:20,337 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 26 [2018-06-18 13:44:20,337 INFO ]: Interpolant automaton has 26 states [2018-06-18 13:44:20,337 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-18 13:44:20,338 INFO ]: CoverageRelationStatistics Valid=81, Invalid=569, Unknown=0, NotChecked=0, Total=650 [2018-06-18 13:44:20,338 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 26 states. [2018-06-18 13:44:20,750 WARN ]: Spent 375.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 46 [2018-06-18 13:44:21,051 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 28 [2018-06-18 13:44:21,196 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 31 [2018-06-18 13:44:21,468 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 30 [2018-06-18 13:44:21,602 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 30 [2018-06-18 13:44:21,783 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 31 [2018-06-18 13:44:22,173 WARN ]: Spent 358.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 44 [2018-06-18 13:44:22,215 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:44:22,215 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-18 13:44:22,215 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-18 13:44:22,215 INFO ]: Start accepts. Automaton has 26 states. Word has length 37 [2018-06-18 13:44:22,215 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:44:22,216 INFO ]: With dead ends: 27 [2018-06-18 13:44:22,216 INFO ]: Without dead ends: 27 [2018-06-18 13:44:22,217 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 25 SyntacticMatches, 5 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=227, Invalid=895, Unknown=0, NotChecked=0, Total=1122 [2018-06-18 13:44:22,217 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-18 13:44:22,220 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-18 13:44:22,220 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-18 13:44:22,225 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-18 13:44:22,225 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-18 13:44:22,225 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:44:22,225 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-18 13:44:22,225 INFO ]: Interpolant automaton has 26 states. [2018-06-18 13:44:22,225 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-18 13:44:22,226 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-18 13:44:22,226 INFO ]: Found error trace [2018-06-18 13:44:22,226 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:44:22,226 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:44:22,226 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-18 13:44:22,226 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:44:22,226 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:44:22,227 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:22,227 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:44:22,227 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:22,340 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:22,343 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:44:23,152 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-18 13:44:23,152 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:44:23,152 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-18 13:44:23,158 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 13:44:23,215 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:44:23,215 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:23,222 INFO ]: Computing forward predicates... [2018-06-18 13:44:23,504 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 35 [2018-06-18 13:44:23,755 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 30 [2018-06-18 13:44:23,981 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 23 [2018-06-18 13:44:24,487 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 25 [2018-06-18 13:44:24,850 WARN ]: Spent 287.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 23 [2018-06-18 13:44:27,167 INFO ]: Checked inductivity of 136 backedges. 0 proven. 100 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-18 13:44:27,188 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:27,188 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 31 [2018-06-18 13:44:27,188 INFO ]: Interpolant automaton has 31 states [2018-06-18 13:44:27,188 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-18 13:44:27,189 INFO ]: CoverageRelationStatistics Valid=86, Invalid=844, Unknown=0, NotChecked=0, Total=930 [2018-06-18 13:44:27,189 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 31 states. [2018-06-18 13:44:27,697 WARN ]: Spent 449.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 60 [2018-06-18 13:44:27,940 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 26 [2018-06-18 13:44:28,237 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 40 [2018-06-18 13:44:28,546 WARN ]: Spent 264.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 40 [2018-06-18 13:44:28,860 WARN ]: Spent 244.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 37 [2018-06-18 13:44:29,133 WARN ]: Spent 240.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 39 [2018-06-18 13:44:29,392 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 40 [2018-06-18 13:44:29,745 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 46 [2018-06-18 13:44:30,133 WARN ]: Spent 352.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 49 [2018-06-18 13:44:30,187 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:44:30,187 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-18 13:44:30,187 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-18 13:44:30,187 INFO ]: Start accepts. Automaton has 31 states. Word has length 41 [2018-06-18 13:44:30,187 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:44:30,188 INFO ]: With dead ends: 29 [2018-06-18 13:44:30,188 INFO ]: Without dead ends: 29 [2018-06-18 13:44:30,189 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=269, Invalid=1291, Unknown=0, NotChecked=0, Total=1560 [2018-06-18 13:44:30,189 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-18 13:44:30,192 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-18 13:44:30,192 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-18 13:44:30,193 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-18 13:44:30,194 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-18 13:44:30,194 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:44:30,194 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-18 13:44:30,194 INFO ]: Interpolant automaton has 31 states. [2018-06-18 13:44:30,194 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-18 13:44:30,195 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-18 13:44:30,195 INFO ]: Found error trace [2018-06-18 13:44:30,195 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:44:30,195 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:44:30,195 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-18 13:44:30,195 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:44:30,195 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:44:30,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:30,196 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:44:30,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:30,291 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:30,292 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:44:31,025 WARN ]: Spent 450.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-18 13:44:31,499 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 27 [2018-06-18 13:44:31,727 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 23 [2018-06-18 13:44:32,191 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-18 13:44:32,191 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:44:32,191 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-18 13:44:32,196 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:44:32,274 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-18 13:44:32,274 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:32,283 INFO ]: Computing forward predicates... [2018-06-18 13:44:32,705 WARN ]: Spent 319.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 32 [2018-06-18 13:44:33,026 WARN ]: Spent 259.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 43 [2018-06-18 13:44:33,276 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 29 [2018-06-18 13:44:33,581 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 23 [2018-06-18 13:44:33,933 WARN ]: Spent 275.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 25 [2018-06-18 13:44:34,131 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 22 [2018-06-18 13:44:34,853 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-18 13:44:34,874 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:34,874 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 34 [2018-06-18 13:44:34,874 INFO ]: Interpolant automaton has 34 states [2018-06-18 13:44:34,874 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-18 13:44:34,874 INFO ]: CoverageRelationStatistics Valid=96, Invalid=1026, Unknown=0, NotChecked=0, Total=1122 [2018-06-18 13:44:34,875 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 34 states. [2018-06-18 13:44:35,686 WARN ]: Spent 759.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 70 [2018-06-18 13:44:36,062 WARN ]: Spent 295.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 26 [2018-06-18 13:44:36,502 WARN ]: Spent 402.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 54 [2018-06-18 13:44:36,940 WARN ]: Spent 399.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 49 [2018-06-18 13:44:37,342 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 41 [2018-06-18 13:44:37,733 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 44 [2018-06-18 13:44:38,146 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 42 [2018-06-18 13:44:38,663 WARN ]: Spent 477.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 54 [2018-06-18 13:44:39,072 WARN ]: Spent 368.00 ms on a formula simplification. DAG size of input: 107 DAG size of output: 43 [2018-06-18 13:44:40,244 WARN ]: Spent 1.12 s on a formula simplification. DAG size of input: 106 DAG size of output: 84 [2018-06-18 13:44:40,285 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:44:40,285 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-18 13:44:40,285 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-18 13:44:40,285 INFO ]: Start accepts. Automaton has 34 states. Word has length 45 [2018-06-18 13:44:40,286 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:44:40,286 INFO ]: With dead ends: 31 [2018-06-18 13:44:40,286 INFO ]: Without dead ends: 31 [2018-06-18 13:44:40,287 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 30 SyntacticMatches, 4 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 8.9s TimeCoverageRelationStatistics Valid=333, Invalid=1647, Unknown=0, NotChecked=0, Total=1980 [2018-06-18 13:44:40,287 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-18 13:44:40,292 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-18 13:44:40,292 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-18 13:44:40,298 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-18 13:44:40,298 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-18 13:44:40,299 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:44:40,299 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-18 13:44:40,299 INFO ]: Interpolant automaton has 34 states. [2018-06-18 13:44:40,299 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-18 13:44:40,300 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-18 13:44:40,300 INFO ]: Found error trace [2018-06-18 13:44:40,300 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:44:40,300 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:44:40,300 INFO ]: Analyzing trace with hash 352352522, now seen corresponding path program 10 times [2018-06-18 13:44:40,300 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:44:40,300 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:44:40,301 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:40,301 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:44:40,301 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:44:40,402 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:40,405 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:44:41,334 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-18 13:44:41,334 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:44:41,334 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-18 13:44:41,340 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:44:41,410 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:44:41,410 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:44:41,417 INFO ]: Computing forward predicates... [2018-06-18 13:44:41,573 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 22 [2018-06-18 13:44:41,897 WARN ]: Spent 267.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 43 [2018-06-18 13:44:42,052 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 29 [2018-06-18 13:44:42,392 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 27 [2018-06-18 13:44:43,099 WARN ]: Spent 580.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 31 [2018-06-18 13:44:43,349 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 23 [2018-06-18 13:44:44,462 INFO ]: Checked inductivity of 210 backedges. 0 proven. 155 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-18 13:44:44,482 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:44:44,482 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 36 [2018-06-18 13:44:44,483 INFO ]: Interpolant automaton has 36 states [2018-06-18 13:44:44,483 INFO ]: Constructing interpolant automaton starting with 36 interpolants. [2018-06-18 13:44:44,483 INFO ]: CoverageRelationStatistics Valid=128, Invalid=1132, Unknown=0, NotChecked=0, Total=1260 [2018-06-18 13:44:44,484 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 36 states. [2018-06-18 13:44:45,335 WARN ]: Spent 792.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 71 [2018-06-18 13:44:45,653 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 27 [2018-06-18 13:44:46,036 WARN ]: Spent 350.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 38 [2018-06-18 13:44:46,585 WARN ]: Spent 514.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 40 [2018-06-18 13:44:46,941 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 39 [2018-06-18 13:44:47,420 WARN ]: Spent 363.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 41 Received shutdown request... [2018-06-18 13:44:47,514 WARN ]: Removed 4 from assertion stack [2018-06-18 13:44:47,515 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:44:47,515 WARN ]: Verification canceled [2018-06-18 13:44:47,518 WARN ]: Timeout [2018-06-18 13:44:47,519 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 01:44:47 BoogieIcfgContainer [2018-06-18 13:44:47,519 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 13:44:47,519 INFO ]: Toolchain (without parser) took 58674.14 ms. Allocated memory was 304.1 MB in the beginning and 821.6 MB in the end (delta: 517.5 MB). Free memory was 256.5 MB in the beginning and 562.2 MB in the end (delta: -305.7 MB). Peak memory consumption was 211.8 MB. Max. memory is 3.6 GB. [2018-06-18 13:44:47,520 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.1 MB. Free memory is still 269.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:44:47,521 INFO ]: ChcToBoogie took 75.10 ms. Allocated memory is still 304.1 MB. Free memory was 256.5 MB in the beginning and 253.5 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:44:47,521 INFO ]: Boogie Preprocessor took 55.43 ms. Allocated memory is still 304.1 MB. Free memory was 253.5 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:44:47,521 INFO ]: RCFGBuilder took 265.15 ms. Allocated memory is still 304.1 MB. Free memory was 251.5 MB in the beginning and 241.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:44:47,523 INFO ]: TraceAbstraction took 58270.71 ms. Allocated memory was 304.1 MB in the beginning and 821.6 MB in the end (delta: 517.5 MB). Free memory was 241.4 MB in the beginning and 562.2 MB in the end (delta: -320.7 MB). Peak memory consumption was 196.8 MB. Max. memory is 3.6 GB. [2018-06-18 13:44:47,525 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.1 MB. Free memory is still 269.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 75.10 ms. Allocated memory is still 304.1 MB. Free memory was 256.5 MB in the beginning and 253.5 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 55.43 ms. Allocated memory is still 304.1 MB. Free memory was 253.5 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 265.15 ms. Allocated memory is still 304.1 MB. Free memory was 251.5 MB in the beginning and 241.4 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58270.71 ms. Allocated memory was 304.1 MB in the beginning and 821.6 MB in the end (delta: 517.5 MB). Free memory was 241.4 MB in the beginning and 562.2 MB in the end (delta: -320.7 MB). Peak memory consumption was 196.8 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 (31states) and interpolant automaton (currently 10 states, 36 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 93. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 58.2s OverallTime, 11 OverallIterations, 11 TraceHistogramMax, 17.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 149 SDtfs, 579 SDslu, 1061 SDs, 0 SdLazy, 965 SolverSat, 708 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 514 GetRequests, 227 SyntacticMatches, 25 SemanticMatches, 261 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1050 ImplicationChecksByTransitivity, 46.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred in iteration=10, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 10 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 38.5s InterpolantComputationTime, 629 NumberOfCodeBlocks, 629 NumberOfCodeBlocksAsserted, 48 NumberOfCheckSat, 608 ConstructedInterpolants, 0 QuantifiedInterpolants, 537760 SizeOfPredicates, 869 NumberOfNonLiveVariables, 2790 ConjunctsInSsa, 557 ConjunctsInUnsatCore, 21 InterpolantComputations, 1 PerfectInterpolantSequences, 440/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/substring1.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_13-44-47-535.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/substring1.c.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_13-44-47-535.csv Completed graceful shutdown