java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:51:06,071 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:51:06,073 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:51:06,084 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:51:06,084 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:51:06,085 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:51:06,086 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:51:06,088 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:51:06,090 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:51:06,090 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:51:06,091 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:51:06,091 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:51:06,092 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:51:06,096 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:51:06,097 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:51:06,097 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:51:06,109 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:51:06,111 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:51:06,113 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:51:06,114 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:51:06,115 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:51:06,122 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:51:06,122 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:51:06,122 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:51:06,123 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:51:06,124 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:51:06,125 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:51:06,125 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:51:06,126 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:51:06,133 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:51:06,134 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:51:06,134 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:51:06,134 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:51:06,135 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:51:06,136 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:51:06,136 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:51:06,155 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:51:06,155 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:51:06,155 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:51:06,155 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:51:06,156 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:51:06,157 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:51:06,157 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:51:06,157 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:51:06,157 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:51:06,157 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:51:06,166 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:51:06,166 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:51:06,166 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:51:06,167 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:51:06,167 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:51:06,167 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:51:06,167 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:51:06,167 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:51:06,167 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:51:06,168 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:51:06,168 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:51:06,169 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:51:06,170 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:51:06,210 INFO ]: Repository-Root is: /tmp [2018-06-25 12:51:06,225 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:51:06,232 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:51:06,234 INFO ]: Initializing SmtParser... [2018-06-25 12:51:06,234 INFO ]: SmtParser initialized [2018-06-25 12:51:06,235 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 [2018-06-25 12:51:06,236 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-25 12:51:06,334 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 unknown [2018-06-25 12:51:06,611 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 [2018-06-25 12:51:06,615 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:51:06,621 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:51:06,621 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:51:06,621 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:51:06,621 INFO ]: ChcToBoogie initialized [2018-06-25 12:51:06,624 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,682 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06 Unit [2018-06-25 12:51:06,683 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:51:06,683 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:51:06,683 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:51:06,683 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:51:06,703 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,704 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,714 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,714 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,721 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,723 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,724 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... [2018-06-25 12:51:06,726 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:51:06,727 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:51:06,727 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:51:06,727 INFO ]: RCFGBuilder initialized [2018-06-25 12:51:06,735 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-25 12:51:06,764 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:51:06,764 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:51:06,764 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:51:06,764 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:51:06,764 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:51:06,764 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:51:06,960 INFO ]: Using library mode [2018-06-25 12:51:06,960 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:51:06 BoogieIcfgContainer [2018-06-25 12:51:06,960 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:51:06,963 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:51:06,963 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:51:06,966 INFO ]: TraceAbstraction initialized [2018-06-25 12:51:06,967 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:51:06" (1/3) ... [2018-06-25 12:51:06,968 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@50070674 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:51:06, skipping insertion in model container [2018-06-25 12:51:06,968 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:51:06" (2/3) ... [2018-06-25 12:51:06,968 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@50070674 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:51:06, skipping insertion in model container [2018-06-25 12:51:06,968 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:51:06" (3/3) ... [2018-06-25 12:51:06,970 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:51:06,980 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:51:06,988 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:51:07,031 INFO ]: Using default assertion order modulation [2018-06-25 12:51:07,032 INFO ]: Interprodecural is true [2018-06-25 12:51:07,032 INFO ]: Hoare is false [2018-06-25 12:51:07,032 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:51:07,032 INFO ]: Backedges is TWOTRACK [2018-06-25 12:51:07,032 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:51:07,032 INFO ]: Difference is false [2018-06-25 12:51:07,032 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:51:07,032 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:51:07,045 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:51:07,061 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:51:07,062 INFO ]: Found error trace [2018-06-25 12:51:07,064 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:07,065 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:07,070 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:51:07,073 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:07,073 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:07,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:07,109 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:07,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:07,147 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:07,235 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:07,237 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:51:07,237 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:51:07,239 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:51:07,256 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:51:07,257 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:51:07,259 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:51:07,343 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:07,344 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:51:07,344 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:51:07,346 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:51:07,346 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:07,359 INFO ]: With dead ends: 9 [2018-06-25 12:51:07,359 INFO ]: Without dead ends: 9 [2018-06-25 12:51:07,361 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:51:07,381 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:51:07,396 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:51:07,398 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:51:07,398 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:51:07,399 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:51:07,399 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:07,399 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:51:07,399 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:51:07,400 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:51:07,400 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:51:07,400 INFO ]: Found error trace [2018-06-25 12:51:07,400 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:07,400 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:07,400 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:51:07,400 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:07,400 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:07,401 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:07,401 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:07,401 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:07,427 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:07,573 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:07,573 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:07,573 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:07,580 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:07,621 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:07,629 INFO ]: Computing forward predicates... [2018-06-25 12:51:08,025 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:08,045 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:08,045 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 12:51:08,046 INFO ]: Interpolant automaton has 5 states [2018-06-25 12:51:08,046 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 12:51:08,046 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 12:51:08,046 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 12:51:08,168 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:08,169 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 12:51:08,169 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 12:51:08,169 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 12:51:08,169 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:08,169 INFO ]: With dead ends: 11 [2018-06-25 12:51:08,169 INFO ]: Without dead ends: 11 [2018-06-25 12:51:08,170 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:51:08,171 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 12:51:08,172 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 12:51:08,172 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 12:51:08,172 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 12:51:08,172 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-25 12:51:08,172 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:08,172 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 12:51:08,172 INFO ]: Interpolant automaton has 5 states. [2018-06-25 12:51:08,172 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 12:51:08,173 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 12:51:08,173 INFO ]: Found error trace [2018-06-25 12:51:08,173 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:08,173 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:08,173 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-25 12:51:08,173 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:08,173 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:08,174 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:08,174 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:08,174 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:08,303 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:08,707 WARN ]: Spent 263.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 15 [2018-06-25 12:51:08,830 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:08,830 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:08,830 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-25 12:51:08,837 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:51:08,911 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:51:08,911 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:08,915 INFO ]: Computing forward predicates... [2018-06-25 12:51:09,714 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:10,816 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:10,837 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:10,837 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-25 12:51:10,837 INFO ]: Interpolant automaton has 8 states [2018-06-25 12:51:10,837 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 12:51:10,837 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:51:10,837 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-25 12:51:11,143 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 17 [2018-06-25 12:51:11,144 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:11,144 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:51:11,144 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 12:51:11,144 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-25 12:51:11,144 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:11,145 INFO ]: With dead ends: 12 [2018-06-25 12:51:11,145 INFO ]: Without dead ends: 12 [2018-06-25 12:51:11,145 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=49, Invalid=83, Unknown=0, NotChecked=0, Total=132 [2018-06-25 12:51:11,145 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:51:11,146 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:51:11,146 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:51:11,147 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:51:11,147 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 12:51:11,147 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:11,147 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:51:11,147 INFO ]: Interpolant automaton has 8 states. [2018-06-25 12:51:11,147 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:51:11,147 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:51:11,147 INFO ]: Found error trace [2018-06-25 12:51:11,148 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:11,148 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:11,148 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-25 12:51:11,148 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:11,148 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:11,149 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:11,149 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:51:11,149 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:11,199 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:11,369 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:11,369 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:11,369 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-25 12:51:11,381 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:51:11,443 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:51:11,443 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:11,448 INFO ]: Computing forward predicates... [2018-06-25 12:51:13,188 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:13,210 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:13,210 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-25 12:51:13,210 INFO ]: Interpolant automaton has 9 states [2018-06-25 12:51:13,210 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 12:51:13,210 INFO ]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-25 12:51:13,211 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-25 12:51:13,432 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:13,432 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 12:51:13,432 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 12:51:13,433 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-25 12:51:13,433 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:13,433 INFO ]: With dead ends: 13 [2018-06-25 12:51:13,433 INFO ]: Without dead ends: 13 [2018-06-25 12:51:13,434 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=65, Invalid=117, Unknown=0, NotChecked=0, Total=182 [2018-06-25 12:51:13,434 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 12:51:13,435 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 12:51:13,435 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 12:51:13,436 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 12:51:13,436 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 12:51:13,436 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:13,436 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 12:51:13,436 INFO ]: Interpolant automaton has 9 states. [2018-06-25 12:51:13,436 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 12:51:13,436 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 12:51:13,437 INFO ]: Found error trace [2018-06-25 12:51:13,437 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:13,437 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:13,437 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 4 times [2018-06-25 12:51:13,437 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:13,437 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:13,437 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:13,437 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:51:13,438 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:13,483 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:13,698 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:13,698 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:13,698 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:13,706 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 12:51:13,757 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:51:13,757 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:13,761 INFO ]: Computing forward predicates... [2018-06-25 12:51:17,334 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:17,354 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:17,354 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-25 12:51:17,354 INFO ]: Interpolant automaton has 10 states [2018-06-25 12:51:17,354 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 12:51:17,354 INFO ]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2018-06-25 12:51:17,355 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-25 12:51:17,645 WARN ]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-25 12:51:17,689 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:17,689 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 12:51:17,689 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 12:51:17,689 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-25 12:51:17,690 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:17,690 INFO ]: With dead ends: 14 [2018-06-25 12:51:17,690 INFO ]: Without dead ends: 14 [2018-06-25 12:51:17,690 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=92, Invalid=148, Unknown=0, NotChecked=0, Total=240 [2018-06-25 12:51:17,690 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 12:51:17,692 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 12:51:17,692 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 12:51:17,692 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 12:51:17,692 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-25 12:51:17,692 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:17,692 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 12:51:17,692 INFO ]: Interpolant automaton has 10 states. [2018-06-25 12:51:17,692 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 12:51:17,693 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 12:51:17,693 INFO ]: Found error trace [2018-06-25 12:51:17,693 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:17,693 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:17,693 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 5 times [2018-06-25 12:51:17,693 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:17,693 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:17,694 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:17,694 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:51:17,694 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:17,769 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:18,054 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:18,054 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:18,054 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:18,061 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 12:51:18,137 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 12:51:18,137 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:18,142 INFO ]: Computing forward predicates... [2018-06-25 12:51:19,869 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:19,890 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:19,890 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-06-25 12:51:19,890 INFO ]: Interpolant automaton has 12 states [2018-06-25 12:51:19,890 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 12:51:19,890 INFO ]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-25 12:51:19,890 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 12 states. [2018-06-25 12:51:20,231 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:20,231 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 12:51:20,231 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 12:51:20,232 INFO ]: Start accepts. Automaton has 12 states. Word has length 13 [2018-06-25 12:51:20,232 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:20,232 INFO ]: With dead ends: 16 [2018-06-25 12:51:20,232 INFO ]: Without dead ends: 16 [2018-06-25 12:51:20,232 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=130, Invalid=250, Unknown=0, NotChecked=0, Total=380 [2018-06-25 12:51:20,233 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 12:51:20,234 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 12:51:20,234 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 12:51:20,234 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 12:51:20,234 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 13 [2018-06-25 12:51:20,234 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:20,234 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 12:51:20,234 INFO ]: Interpolant automaton has 12 states. [2018-06-25 12:51:20,234 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 12:51:20,236 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 12:51:20,236 INFO ]: Found error trace [2018-06-25 12:51:20,236 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:20,236 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:20,236 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 6 times [2018-06-25 12:51:20,236 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:20,236 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:20,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:20,237 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:51:20,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:20,324 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:20,963 WARN ]: Spent 392.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 7 [2018-06-25 12:51:21,341 WARN ]: Spent 307.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 12:51:21,580 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-25 12:51:21,591 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:21,591 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:21,591 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:21,609 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 12:51:21,690 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-25 12:51:21,690 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:21,694 INFO ]: Computing forward predicates... [2018-06-25 12:51:25,618 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:25,640 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:25,640 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 14 [2018-06-25 12:51:25,640 INFO ]: Interpolant automaton has 14 states [2018-06-25 12:51:25,640 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-25 12:51:25,641 INFO ]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2018-06-25 12:51:25,641 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 14 states. [2018-06-25 12:51:26,057 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:26,058 INFO ]: Finished difference Result 18 states and 18 transitions. [2018-06-25 12:51:26,058 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-25 12:51:26,058 INFO ]: Start accepts. Automaton has 14 states. Word has length 15 [2018-06-25 12:51:26,058 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:26,058 INFO ]: With dead ends: 18 [2018-06-25 12:51:26,058 INFO ]: Without dead ends: 18 [2018-06-25 12:51:26,059 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=173, Invalid=333, Unknown=0, NotChecked=0, Total=506 [2018-06-25 12:51:26,059 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-25 12:51:26,060 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-25 12:51:26,060 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-25 12:51:26,061 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-06-25 12:51:26,061 INFO ]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 15 [2018-06-25 12:51:26,061 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:26,061 INFO ]: Abstraction has 18 states and 18 transitions. [2018-06-25 12:51:26,061 INFO ]: Interpolant automaton has 14 states. [2018-06-25 12:51:26,061 INFO ]: Start isEmpty. Operand 18 states and 18 transitions. [2018-06-25 12:51:26,061 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-25 12:51:26,061 INFO ]: Found error trace [2018-06-25 12:51:26,061 INFO ]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:26,062 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:26,062 INFO ]: Analyzing trace with hash 1509090572, now seen corresponding path program 7 times [2018-06-25 12:51:26,062 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:26,062 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:26,062 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:26,062 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:51:26,062 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:26,252 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:26,881 INFO ]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:26,881 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:26,881 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:26,889 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:26,947 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:26,952 INFO ]: Computing forward predicates... [2018-06-25 12:51:28,774 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:28,811 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:34,854 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:37,274 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 20 [2018-06-25 12:51:37,499 INFO ]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:37,519 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:51:37,519 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-06-25 12:51:37,519 INFO ]: Interpolant automaton has 18 states [2018-06-25 12:51:37,519 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-25 12:51:37,520 INFO ]: CoverageRelationStatistics Valid=76, Invalid=230, Unknown=0, NotChecked=0, Total=306 [2018-06-25 12:51:37,520 INFO ]: Start difference. First operand 18 states and 18 transitions. Second operand 18 states. [2018-06-25 12:51:37,877 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 35 [2018-06-25 12:51:38,197 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 30 [2018-06-25 12:51:38,480 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-25 12:51:38,599 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:51:38,599 INFO ]: Finished difference Result 19 states and 19 transitions. [2018-06-25 12:51:38,599 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-25 12:51:38,599 INFO ]: Start accepts. Automaton has 18 states. Word has length 17 [2018-06-25 12:51:38,599 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:51:38,600 INFO ]: With dead ends: 19 [2018-06-25 12:51:38,600 INFO ]: Without dead ends: 19 [2018-06-25 12:51:38,600 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=265, Invalid=547, Unknown=0, NotChecked=0, Total=812 [2018-06-25 12:51:38,600 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-25 12:51:38,603 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-25 12:51:38,603 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-25 12:51:38,603 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-06-25 12:51:38,603 INFO ]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 17 [2018-06-25 12:51:38,603 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:51:38,603 INFO ]: Abstraction has 19 states and 19 transitions. [2018-06-25 12:51:38,603 INFO ]: Interpolant automaton has 18 states. [2018-06-25 12:51:38,603 INFO ]: Start isEmpty. Operand 19 states and 19 transitions. [2018-06-25 12:51:38,604 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-25 12:51:38,604 INFO ]: Found error trace [2018-06-25 12:51:38,604 INFO ]: trace histogram [11, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:51:38,604 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:51:38,604 INFO ]: Analyzing trace with hash -464714988, now seen corresponding path program 8 times [2018-06-25 12:51:38,604 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:51:38,604 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:51:38,605 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:38,605 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:51:38,605 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:51:38,715 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:39,363 WARN ]: Spent 387.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 6 [2018-06-25 12:51:39,740 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:51:39,740 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:51:39,740 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:51:39,747 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:51:39,819 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:51:39,819 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:51:39,825 INFO ]: Computing forward predicates... [2018-06-25 12:51:40,875 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:45,199 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:51:45,245 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:51:58,457 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 12:52:09,868 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 12:52:09,874 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 12:52:10,949 INFO ]: Timeout while computing interpolants [2018-06-25 12:52:11,149 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:52:11,149 WARN ]: Verification canceled [2018-06-25 12:52:11,155 WARN ]: Timeout [2018-06-25 12:52:11,156 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:52:11 BoogieIcfgContainer [2018-06-25 12:52:11,156 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:52:11,157 INFO ]: Toolchain (without parser) took 64540.76 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 259.1 MB in the beginning and 915.5 MB in the end (delta: -656.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:52:11,158 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 306.7 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:52:11,158 INFO ]: ChcToBoogie took 61.74 ms. Allocated memory is still 306.7 MB. Free memory was 259.1 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:52:11,158 INFO ]: Boogie Preprocessor took 43.05 ms. Allocated memory is still 306.7 MB. Free memory was 257.1 MB in the beginning and 255.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:52:11,162 INFO ]: RCFGBuilder took 233.37 ms. Allocated memory is still 306.7 MB. Free memory was 255.1 MB in the beginning and 247.1 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:52:11,163 INFO ]: TraceAbstraction took 64193.24 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 247.1 MB in the beginning and 915.5 MB in the end (delta: -668.3 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:52:11,174 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 306.7 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 61.74 ms. Allocated memory is still 306.7 MB. Free memory was 259.1 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 43.05 ms. Allocated memory is still 306.7 MB. Free memory was 257.1 MB in the beginning and 255.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 233.37 ms. Allocated memory is still 306.7 MB. Free memory was 255.1 MB in the beginning and 247.1 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64193.24 ms. Allocated memory was 306.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 247.1 MB in the beginning and 915.5 MB in the end (delta: -668.3 MB). Peak memory consumption was 1.3 GB. 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 19 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 12186 quantified variables from 13 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 64.1s OverallTime, 9 OverallIterations, 11 TraceHistogramMax, 2.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 29 SDslu, 219 SDs, 0 SdLazy, 89 SolverSat, 57 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 184 GetRequests, 51 SyntacticMatches, 26 SemanticMatches, 107 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 445 ImplicationChecksByTransitivity, 6.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=8, 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, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 27.1s InterpolantComputationTime, 179 NumberOfCodeBlocks, 179 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 164 ConstructedInterpolants, 0 QuantifiedInterpolants, 13193 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1513 ConjunctsInSsa, 370 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/288 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/dillig05.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-52-11-189.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig05.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-52-11-189.csv Completed graceful shutdown