java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:47:12,251 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:47:12,283 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:47:12,295 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:47:12,295 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:47:12,296 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:47:12,297 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:47:12,300 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:47:12,301 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:47:12,302 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:47:12,303 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:47:12,304 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:47:12,305 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:47:12,306 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:47:12,307 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:47:12,308 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:47:12,312 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:47:12,314 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:47:12,315 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:47:12,316 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:47:12,317 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:47:12,319 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:47:12,320 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:47:12,320 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:47:12,321 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:47:12,322 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:47:12,322 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:47:12,323 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:47:12,324 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:47:12,324 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:47:12,325 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:47:12,325 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:47:12,326 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:47:12,326 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:47:12,327 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:47:12,327 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:47:12,358 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:47:12,359 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:47:12,359 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:47:12,359 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:47:12,360 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:47:12,361 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:47:12,361 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:47:12,361 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:47:12,361 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:47:12,361 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:47:12,362 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:47:12,362 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:47:12,362 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:47:12,362 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:47:12,362 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:47:12,362 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:47:12,363 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:47:12,364 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:47:12,364 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:47:12,420 INFO ]: Repository-Root is: /tmp [2018-06-22 05:47:12,438 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:47:12,443 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:47:12,445 INFO ]: Initializing SmtParser... [2018-06-22 05:47:12,445 INFO ]: SmtParser initialized [2018-06-22 05:47:12,446 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 [2018-06-22 05:47:12,447 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 05:47:13,262 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 unknown [2018-06-22 05:47:13,924 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_loop.c.smt2 [2018-06-22 05:47:13,930 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:47:13,939 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:47:13,939 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:47:13,939 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:47:13,939 INFO ]: ChcToBoogie initialized [2018-06-22 05:47:14,015 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:47:13" (1/1) ... [2018-06-22 05:47:14,134 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14 Unit [2018-06-22 05:47:14,134 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:47:14,134 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:47:14,134 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:47:14,134 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:47:14,195 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,195 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,200 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,201 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,206 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,209 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,210 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (1/1) ... [2018-06-22 05:47:14,212 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:47:14,213 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:47:14,213 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:47:14,213 INFO ]: RCFGBuilder initialized [2018-06-22 05:47:14,214 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (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) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:47:14,226 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:47:14,226 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:47:14,226 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:47:14,226 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:47:14,226 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:47:14,226 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 05:47:14,506 INFO ]: Using library mode [2018-06-22 05:47:14,507 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:47:14 BoogieIcfgContainer [2018-06-22 05:47:14,507 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:47:14,508 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:47:14,508 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:47:14,581 INFO ]: TraceAbstraction initialized [2018-06-22 05:47:14,581 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:47:13" (1/3) ... [2018-06-22 05:47:14,582 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@182cf704 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:47:14, skipping insertion in model container [2018-06-22 05:47:14,582 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:47:14" (2/3) ... [2018-06-22 05:47:14,582 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@182cf704 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:47:14, skipping insertion in model container [2018-06-22 05:47:14,582 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:47:14" (3/3) ... [2018-06-22 05:47:14,584 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:47:14,695 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:47:14,702 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:47:15,008 INFO ]: Using default assertion order modulation [2018-06-22 05:47:15,009 INFO ]: Interprodecural is true [2018-06-22 05:47:15,009 INFO ]: Hoare is false [2018-06-22 05:47:15,009 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:47:15,009 INFO ]: Backedges is TWOTRACK [2018-06-22 05:47:15,009 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:47:15,009 INFO ]: Difference is false [2018-06-22 05:47:15,009 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:47:15,009 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:47:15,025 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:47:15,039 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:47:15,039 INFO ]: Found error trace [2018-06-22 05:47:15,039 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:15,040 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:15,044 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 05:47:15,045 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:15,045 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:15,078 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:15,078 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:47:15,079 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:15,129 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:15,261 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:15,264 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:47:15,264 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:47:15,266 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:47:15,277 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:47:15,277 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:47:15,279 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:47:15,351 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:15,351 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:47:15,351 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:47:15,353 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:47:15,353 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:15,361 INFO ]: With dead ends: 9 [2018-06-22 05:47:15,361 INFO ]: Without dead ends: 9 [2018-06-22 05:47:15,363 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:47:15,377 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:47:15,400 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:47:15,401 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:47:15,402 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:47:15,403 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:47:15,403 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:15,403 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:47:15,403 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:47:15,403 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:47:15,403 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:47:15,404 INFO ]: Found error trace [2018-06-22 05:47:15,404 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:15,404 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:15,404 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 05:47:15,404 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:15,404 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:15,405 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:15,405 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:47:15,405 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:15,436 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:15,594 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:15,594 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:15,594 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:15,611 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:47:15,675 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:15,686 INFO ]: Computing forward predicates... [2018-06-22 05:47:16,503 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:16,656 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:16,656 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 05:47:16,656 INFO ]: Interpolant automaton has 4 states [2018-06-22 05:47:16,657 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 05:47:16,657 INFO ]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-06-22 05:47:16,657 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 4 states. [2018-06-22 05:47:16,746 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:16,746 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:47:16,747 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 05:47:16,747 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-22 05:47:16,747 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:16,748 INFO ]: With dead ends: 10 [2018-06-22 05:47:16,748 INFO ]: Without dead ends: 10 [2018-06-22 05:47:16,749 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-06-22 05:47:16,749 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:47:16,750 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:47:16,750 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:47:16,750 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:47:16,750 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:47:16,750 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:16,750 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:47:16,750 INFO ]: Interpolant automaton has 4 states. [2018-06-22 05:47:16,750 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:47:16,750 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:47:16,751 INFO ]: Found error trace [2018-06-22 05:47:16,751 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:16,752 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:16,752 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 05:47:16,752 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:16,752 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:16,753 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:16,753 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:47:16,753 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:16,845 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:17,322 WARN ]: Spent 301.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 05:47:17,354 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:17,354 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:17,354 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:17,362 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:47:17,410 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:47:17,410 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:17,413 INFO ]: Computing forward predicates... [2018-06-22 05:47:19,502 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:19,525 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:19,525 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:47:19,525 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:47:19,525 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:47:19,525 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:47:19,526 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:47:19,587 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:19,587 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:47:19,589 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:47:19,589 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:47:19,589 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:19,590 INFO ]: With dead ends: 11 [2018-06-22 05:47:19,590 INFO ]: Without dead ends: 11 [2018-06-22 05:47:19,590 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:47:19,590 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:47:19,591 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:47:19,592 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:47:19,592 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:47:19,592 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 05:47:19,592 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:19,592 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:47:19,592 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:47:19,592 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:47:19,593 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:47:19,593 INFO ]: Found error trace [2018-06-22 05:47:19,593 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:19,593 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:19,593 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-22 05:47:19,593 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:19,593 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:19,594 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:19,594 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:47:19,594 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:19,657 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:19,764 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:19,764 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:19,764 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:19,770 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:47:19,816 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:47:19,816 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:19,819 INFO ]: Computing forward predicates... [2018-06-22 05:47:22,737 WARN ]: Spent 427.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 8 [2018-06-22 05:47:25,632 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:25,651 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:25,651 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 05:47:25,651 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:47:25,651 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:47:25,652 INFO ]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:47:25,652 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-22 05:47:25,786 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:25,786 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 05:47:25,786 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 05:47:25,786 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 05:47:25,786 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:25,787 INFO ]: With dead ends: 12 [2018-06-22 05:47:25,787 INFO ]: Without dead ends: 12 [2018-06-22 05:47:25,787 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2018-06-22 05:47:25,787 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 05:47:25,789 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 05:47:25,789 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 05:47:25,790 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 05:47:25,790 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 05:47:25,790 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:25,790 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 05:47:25,790 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:47:25,790 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 05:47:25,790 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 05:47:25,790 INFO ]: Found error trace [2018-06-22 05:47:25,790 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:25,790 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:25,790 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 4 times [2018-06-22 05:47:25,790 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:25,790 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:25,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:25,791 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:47:25,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:25,876 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:26,126 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:26,126 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:26,126 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:26,132 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:47:26,199 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:47:26,199 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:26,203 INFO ]: Computing forward predicates... [2018-06-22 05:47:28,018 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:47:42,636 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:42,655 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:42,655 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-22 05:47:42,656 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:47:42,656 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:47:42,656 INFO ]: CoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:47:42,656 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-22 05:47:42,820 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:42,820 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:47:42,820 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:47:42,820 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-22 05:47:42,820 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:42,820 INFO ]: With dead ends: 13 [2018-06-22 05:47:42,820 INFO ]: Without dead ends: 13 [2018-06-22 05:47:42,821 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=65, Invalid=91, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:47:42,821 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:47:42,822 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:47:42,822 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:47:42,822 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:47:42,822 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 05:47:42,823 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:42,823 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:47:42,823 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:47:42,823 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:47:42,823 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:47:42,823 INFO ]: Found error trace [2018-06-22 05:47:42,823 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:42,823 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:42,823 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 5 times [2018-06-22 05:47:42,823 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:42,823 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:42,825 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:42,826 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:47:42,826 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:42,873 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:43,182 WARN ]: Spent 126.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 05:47:43,240 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:43,240 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:43,240 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:43,248 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 05:47:43,360 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 05:47:43,360 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:43,364 INFO ]: Computing forward predicates... [2018-06-22 05:47:45,555 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:47:46,203 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:46,223 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:46,223 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 05:47:46,223 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:47:46,224 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:47:46,224 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:47:46,224 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 8 states. [2018-06-22 05:47:46,463 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:46,463 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 05:47:46,463 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 05:47:46,463 INFO ]: Start accepts. Automaton has 8 states. Word has length 12 [2018-06-22 05:47:46,463 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:46,463 INFO ]: With dead ends: 14 [2018-06-22 05:47:46,463 INFO ]: Without dead ends: 14 [2018-06-22 05:47:46,464 INFO ]: 0 DeclaredPredicates, 24 GetRequests, 8 SyntacticMatches, 5 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:47:46,464 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 05:47:46,465 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 05:47:46,465 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 05:47:46,465 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 05:47:46,465 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 05:47:46,466 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:46,466 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 05:47:46,466 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:47:46,466 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 05:47:46,466 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 05:47:46,466 INFO ]: Found error trace [2018-06-22 05:47:46,466 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:46,466 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:46,466 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 6 times [2018-06-22 05:47:46,466 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:46,466 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:46,467 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:46,467 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:47:46,467 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:46,548 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:46,779 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 05:47:47,264 WARN ]: Spent 424.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 05:47:47,512 WARN ]: Spent 173.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 05:47:47,607 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:47,607 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:47,607 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:47,615 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 05:47:47,675 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 05:47:47,675 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:47,680 INFO ]: Computing forward predicates... [2018-06-22 05:47:48,082 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:47:50,503 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:47:52,131 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:52,255 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:52,255 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-06-22 05:47:52,256 INFO ]: Interpolant automaton has 10 states [2018-06-22 05:47:52,256 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 05:47:52,256 INFO ]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:47:52,256 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 10 states. [2018-06-22 05:47:52,585 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:52,585 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-22 05:47:52,585 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 05:47:52,585 INFO ]: Start accepts. Automaton has 10 states. Word has length 13 [2018-06-22 05:47:52,585 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:52,586 INFO ]: With dead ends: 15 [2018-06-22 05:47:52,586 INFO ]: Without dead ends: 15 [2018-06-22 05:47:52,586 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 56 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=99, Invalid=173, Unknown=0, NotChecked=0, Total=272 [2018-06-22 05:47:52,586 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 05:47:52,588 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 05:47:52,588 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 05:47:52,588 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-22 05:47:52,588 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-22 05:47:52,588 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:52,588 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-22 05:47:52,588 INFO ]: Interpolant automaton has 10 states. [2018-06-22 05:47:52,588 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-22 05:47:52,589 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 05:47:52,589 INFO ]: Found error trace [2018-06-22 05:47:52,589 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:52,589 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:52,589 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 7 times [2018-06-22 05:47:52,589 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:52,589 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:52,589 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:52,589 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:47:52,589 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:52,650 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:53,017 WARN ]: Spent 190.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 05:47:53,121 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:53,135 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:47:53,135 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:47:53,143 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:47:53,197 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:47:53,201 INFO ]: Computing forward predicates... [2018-06-22 05:47:59,535 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:47:59,573 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:47:59,573 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 12 [2018-06-22 05:47:59,573 INFO ]: Interpolant automaton has 12 states [2018-06-22 05:47:59,573 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 05:47:59,573 INFO ]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 05:47:59,573 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 12 states. [2018-06-22 05:47:59,766 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 11 [2018-06-22 05:47:59,975 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:47:59,975 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-22 05:47:59,975 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 05:47:59,975 INFO ]: Start accepts. Automaton has 12 states. Word has length 14 [2018-06-22 05:47:59,975 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:47:59,976 INFO ]: With dead ends: 16 [2018-06-22 05:47:59,976 INFO ]: Without dead ends: 16 [2018-06-22 05:47:59,976 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=127, Invalid=253, Unknown=0, NotChecked=0, Total=380 [2018-06-22 05:47:59,976 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-22 05:47:59,977 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-22 05:47:59,978 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-22 05:47:59,978 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-22 05:47:59,978 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-06-22 05:47:59,978 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:47:59,978 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-22 05:47:59,978 INFO ]: Interpolant automaton has 12 states. [2018-06-22 05:47:59,978 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-22 05:47:59,979 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-22 05:47:59,979 INFO ]: Found error trace [2018-06-22 05:47:59,979 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:47:59,979 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:47:59,979 INFO ]: Analyzing trace with hash 39881678, now seen corresponding path program 8 times [2018-06-22 05:47:59,979 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:47:59,979 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:47:59,979 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:47:59,980 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:47:59,980 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:48:00,042 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:48:00,549 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:48:00,549 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:48:00,549 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:48:00,556 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:48:00,633 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:48:00,633 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:48:00,638 INFO ]: Computing forward predicates... [2018-06-22 05:48:01,974 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:01,978 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:01,985 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:01,988 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:01,991 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:01,995 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:48:02,017 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:02,025 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:02,030 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:48:02,039 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-22 05:48:20,026 INFO ]: Timeout while computing interpolants [2018-06-22 05:48:20,226 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:48:20,226 WARN ]: Verification canceled [2018-06-22 05:48:20,290 WARN ]: Timeout [2018-06-22 05:48:20,291 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:48:20 BoogieIcfgContainer [2018-06-22 05:48:20,291 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:48:20,421 INFO ]: Toolchain (without parser) took 66490.25 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 261.3 MB in the beginning and 1.2 GB in the end (delta: -983.7 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:48:20,422 INFO ]: SmtParser took 0.13 ms. Allocated memory is still 308.8 MB. Free memory is still 274.4 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:48:20,422 INFO ]: ChcToBoogie took 195.00 ms. Allocated memory is still 308.8 MB. Free memory was 261.3 MB in the beginning and 258.4 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:48:20,422 INFO ]: Boogie Preprocessor took 77.75 ms. Allocated memory is still 308.8 MB. Free memory was 258.4 MB in the beginning and 257.4 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-22 05:48:20,423 INFO ]: RCFGBuilder took 294.01 ms. Allocated memory is still 308.8 MB. Free memory was 257.4 MB in the beginning and 246.4 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:48:20,423 INFO ]: TraceAbstraction took 65782.39 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 246.4 MB in the beginning and 1.2 GB in the end (delta: -998.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 05:48:20,426 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.13 ms. Allocated memory is still 308.8 MB. Free memory is still 274.4 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 195.00 ms. Allocated memory is still 308.8 MB. Free memory was 261.3 MB in the beginning and 258.4 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 77.75 ms. Allocated memory is still 308.8 MB. Free memory was 258.4 MB in the beginning and 257.4 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 294.01 ms. Allocated memory is still 308.8 MB. Free memory was 257.4 MB in the beginning and 246.4 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 65782.39 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 246.4 MB in the beginning and 1.2 GB in the end (delta: -998.6 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 16 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 21 quantified variables from 15 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 65.2s OverallTime, 9 OverallIterations, 8 TraceHistogramMax, 1.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 22 SDslu, 161 SDs, 0 SdLazy, 66 SolverSat, 51 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 153 GetRequests, 53 SyntacticMatches, 26 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 4.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=16occurred 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.8s SatisfiabilityAnalysisTime, 41.8s InterpolantComputationTime, 161 NumberOfCodeBlocks, 161 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 146 ConstructedInterpolants, 0 QuantifiedInterpolants, 8324 SizeOfPredicates, 35 NumberOfNonLiveVariables, 1449 ConjunctsInSsa, 255 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/168 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/NetBSD_loop.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-48-20-438.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/NetBSD_loop.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-48-20-438.csv Completed graceful shutdown