java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.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/nest-len.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 01:18:29,225 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 01:18:29,227 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 01:18:29,239 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 01:18:29,240 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 01:18:29,240 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 01:18:29,244 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 01:18:29,247 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 01:18:29,249 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 01:18:29,250 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 01:18:29,251 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 01:18:29,251 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 01:18:29,252 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 01:18:29,256 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 01:18:29,257 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 01:18:29,257 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 01:18:29,262 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 01:18:29,264 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 01:18:29,275 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 01:18:29,276 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 01:18:29,277 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 01:18:29,279 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 01:18:29,279 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 01:18:29,280 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 01:18:29,280 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 01:18:29,281 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 01:18:29,282 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 01:18:29,282 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 01:18:29,283 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 01:18:29,284 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 01:18:29,284 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 01:18:29,285 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 01:18:29,285 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 01:18:29,286 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 01:18:29,286 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 01:18:29,292 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 01:18:29,307 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 01:18:29,307 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 01:18:29,307 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 01:18:29,307 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 01:18:29,308 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 01:18:29,309 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 01:18:29,309 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 01:18:29,309 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 01:18:29,309 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 01:18:29,309 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 01:18:29,310 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 01:18:29,310 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 01:18:29,310 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 01:18:29,310 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 01:18:29,310 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 01:18:29,310 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 01:18:29,311 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 01:18:29,311 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 01:18:29,311 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 01:18:29,311 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 01:18:29,311 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 01:18:29,313 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 01:18:29,313 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 01:18:29,357 INFO ]: Repository-Root is: /tmp [2018-06-25 01:18:29,375 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 01:18:29,378 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 01:18:29,379 INFO ]: Initializing SmtParser... [2018-06-25 01:18:29,380 INFO ]: SmtParser initialized [2018-06-25 01:18:29,380 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-len.c.smt2 [2018-06-25 01:18:29,383 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 01:18:29,471 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-len.c.smt2 unknown [2018-06-25 01:18:29,807 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-len.c.smt2 [2018-06-25 01:18:29,811 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 01:18:29,816 INFO ]: Walking toolchain with 5 elements. [2018-06-25 01:18:29,817 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 01:18:29,817 INFO ]: Initializing ChcToBoogie... [2018-06-25 01:18:29,817 INFO ]: ChcToBoogie initialized [2018-06-25 01:18:29,820 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,869 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29 Unit [2018-06-25 01:18:29,869 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 01:18:29,870 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 01:18:29,870 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 01:18:29,870 INFO ]: Boogie Preprocessor initialized [2018-06-25 01:18:29,890 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,890 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,899 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,899 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,922 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,923 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,925 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (1/1) ... [2018-06-25 01:18:29,927 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 01:18:29,928 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 01:18:29,928 INFO ]: Initializing RCFGBuilder... [2018-06-25 01:18:29,928 INFO ]: RCFGBuilder initialized [2018-06-25 01:18:29,929 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (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 01:18:29,941 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 01:18:29,941 INFO ]: Found specification of procedure gotoProc [2018-06-25 01:18:29,941 INFO ]: Found implementation of procedure gotoProc [2018-06-25 01:18:29,941 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 01:18:29,941 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 01:18:29,941 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 01:18:30,235 INFO ]: Using library mode [2018-06-25 01:18:30,236 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:18:30 BoogieIcfgContainer [2018-06-25 01:18:30,236 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 01:18:30,236 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-25 01:18:30,236 INFO ]: Initializing BlockEncodingV2... [2018-06-25 01:18:30,246 INFO ]: BlockEncodingV2 initialized [2018-06-25 01:18:30,247 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:18:30" (1/1) ... [2018-06-25 01:18:30,273 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-25 01:18:30,274 INFO ]: Using Remove infeasible edges [2018-06-25 01:18:30,275 INFO ]: Using Maximize final states [2018-06-25 01:18:30,275 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-25 01:18:30,275 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-25 01:18:30,278 INFO ]: Using Remove sink states [2018-06-25 01:18:30,279 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-25 01:18:30,279 INFO ]: Using Use SBE [2018-06-25 01:18:30,286 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:18:30,304 WARN ]: aborting because of expected exponential blowup for input size 53 [2018-06-25 01:18:30,305 INFO ]: SBE split 0 edges [2018-06-25 01:18:30,314 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-25 01:18:30,317 INFO ]: 0 new accepting states [2018-06-25 01:18:30,358 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-25 01:18:30,360 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-25 01:18:30,363 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-25 01:18:30,363 INFO ]: 0 new accepting states [2018-06-25 01:18:30,364 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-25 01:18:30,364 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-25 01:18:30,364 INFO ]: Encoded RCFG 6 locations, 6 edges [2018-06-25 01:18:30,364 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 25.06 01:18:30 BasicIcfg [2018-06-25 01:18:30,364 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-25 01:18:30,366 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 01:18:30,366 INFO ]: Initializing TraceAbstraction... [2018-06-25 01:18:30,369 INFO ]: TraceAbstraction initialized [2018-06-25 01:18:30,369 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:18:29" (1/4) ... [2018-06-25 01:18:30,370 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77b3f428 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:18:30, skipping insertion in model container [2018-06-25 01:18:30,370 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:18:29" (2/4) ... [2018-06-25 01:18:30,370 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77b3f428 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:18:30, skipping insertion in model container [2018-06-25 01:18:30,370 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:18:30" (3/4) ... [2018-06-25 01:18:30,370 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@77b3f428 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:18:30, skipping insertion in model container [2018-06-25 01:18:30,371 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 25.06 01:18:30" (4/4) ... [2018-06-25 01:18:30,372 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-25 01:18:30,382 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 01:18:30,390 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 01:18:30,438 INFO ]: Using default assertion order modulation [2018-06-25 01:18:30,438 INFO ]: Interprodecural is true [2018-06-25 01:18:30,438 INFO ]: Hoare is false [2018-06-25 01:18:30,438 INFO ]: Compute interpolants for FPandBP [2018-06-25 01:18:30,438 INFO ]: Backedges is TWOTRACK [2018-06-25 01:18:30,439 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 01:18:30,439 INFO ]: Difference is false [2018-06-25 01:18:30,439 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 01:18:30,439 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 01:18:30,459 INFO ]: Start isEmpty. Operand 6 states. [2018-06-25 01:18:30,477 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-25 01:18:30,477 INFO ]: Found error trace [2018-06-25 01:18:30,477 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-25 01:18:30,478 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:30,483 INFO ]: Analyzing trace with hash 35402562, now seen corresponding path program 1 times [2018-06-25 01:18:30,485 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:30,485 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:30,522 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:30,522 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:18:30,522 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:30,561 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:30,617 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:30,620 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 01:18:30,620 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 01:18:30,621 INFO ]: Interpolant automaton has 3 states [2018-06-25 01:18:30,631 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 01:18:30,631 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 01:18:30,634 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-25 01:18:30,715 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:18:30,715 INFO ]: Finished difference Result 7 states and 7 transitions. [2018-06-25 01:18:30,715 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 01:18:30,716 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-25 01:18:30,717 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:18:30,723 INFO ]: With dead ends: 7 [2018-06-25 01:18:30,723 INFO ]: Without dead ends: 7 [2018-06-25 01:18:30,724 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 01:18:30,736 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-25 01:18:30,749 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-25 01:18:30,750 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-25 01:18:30,750 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-06-25 01:18:30,751 INFO ]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-06-25 01:18:30,751 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:18:30,752 INFO ]: Abstraction has 7 states and 7 transitions. [2018-06-25 01:18:30,752 INFO ]: Interpolant automaton has 3 states. [2018-06-25 01:18:30,752 INFO ]: Start isEmpty. Operand 7 states and 7 transitions. [2018-06-25 01:18:30,752 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-25 01:18:30,752 INFO ]: Found error trace [2018-06-25 01:18:30,752 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-25 01:18:30,752 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:30,752 INFO ]: Analyzing trace with hash 1097183593, now seen corresponding path program 1 times [2018-06-25 01:18:30,753 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:30,753 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:30,754 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:30,754 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:18:30,754 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:30,827 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:31,159 WARN ]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 01:18:31,160 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:31,160 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:18:31,160 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 01:18:31,175 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:18:31,222 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:31,229 INFO ]: Computing forward predicates... [2018-06-25 01:18:31,730 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:31,762 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:18:31,762 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 01:18:31,762 INFO ]: Interpolant automaton has 5 states [2018-06-25 01:18:31,762 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 01:18:31,763 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 01:18:31,763 INFO ]: Start difference. First operand 7 states and 7 transitions. Second operand 5 states. [2018-06-25 01:18:31,946 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:18:31,947 INFO ]: Finished difference Result 8 states and 8 transitions. [2018-06-25 01:18:31,947 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 01:18:31,947 INFO ]: Start accepts. Automaton has 5 states. Word has length 6 [2018-06-25 01:18:31,947 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:18:31,948 INFO ]: With dead ends: 8 [2018-06-25 01:18:31,948 INFO ]: Without dead ends: 8 [2018-06-25 01:18:31,948 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 01:18:31,949 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-25 01:18:31,949 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-25 01:18:31,950 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-25 01:18:31,950 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-06-25 01:18:31,950 INFO ]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-06-25 01:18:31,950 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:18:31,950 INFO ]: Abstraction has 8 states and 8 transitions. [2018-06-25 01:18:31,950 INFO ]: Interpolant automaton has 5 states. [2018-06-25 01:18:31,950 INFO ]: Start isEmpty. Operand 8 states and 8 transitions. [2018-06-25 01:18:31,950 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 01:18:31,950 INFO ]: Found error trace [2018-06-25 01:18:31,950 INFO ]: trace histogram [2, 1, 1, 1, 1, 1] [2018-06-25 01:18:31,950 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:31,951 INFO ]: Analyzing trace with hash -347342814, now seen corresponding path program 2 times [2018-06-25 01:18:31,951 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:31,951 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:31,951 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:31,951 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 01:18:31,951 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:32,066 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:32,402 WARN ]: Spent 133.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 01:18:32,436 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:32,437 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:18:32,437 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 01:18:32,445 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 01:18:32,542 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 01:18:32,542 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:32,545 INFO ]: Computing forward predicates... [2018-06-25 01:18:34,424 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:34,444 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:18:34,454 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 01:18:34,454 INFO ]: Interpolant automaton has 6 states [2018-06-25 01:18:34,454 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 01:18:34,454 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 01:18:34,454 INFO ]: Start difference. First operand 8 states and 8 transitions. Second operand 6 states. [2018-06-25 01:18:34,571 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:18:34,571 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 01:18:34,571 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 01:18:34,571 INFO ]: Start accepts. Automaton has 6 states. Word has length 7 [2018-06-25 01:18:34,572 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:18:34,572 INFO ]: With dead ends: 9 [2018-06-25 01:18:34,572 INFO ]: Without dead ends: 9 [2018-06-25 01:18:34,572 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 6 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-25 01:18:34,572 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 01:18:34,573 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 01:18:34,573 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 01:18:34,574 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 01:18:34,574 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 01:18:34,574 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:18:34,574 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 01:18:34,574 INFO ]: Interpolant automaton has 6 states. [2018-06-25 01:18:34,574 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 01:18:34,574 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 01:18:34,574 INFO ]: Found error trace [2018-06-25 01:18:34,574 INFO ]: trace histogram [3, 1, 1, 1, 1, 1] [2018-06-25 01:18:34,574 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:34,574 INFO ]: Analyzing trace with hash 2116978825, now seen corresponding path program 3 times [2018-06-25 01:18:34,574 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:34,574 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:34,575 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:34,575 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:18:34,575 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:34,613 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:34,899 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:34,899 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:18:34,899 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 01:18:34,908 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 01:18:35,006 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 01:18:35,006 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:35,010 INFO ]: Computing forward predicates... [2018-06-25 01:18:40,681 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:40,701 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:18:40,701 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 01:18:40,701 INFO ]: Interpolant automaton has 7 states [2018-06-25 01:18:40,701 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 01:18:40,701 INFO ]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2018-06-25 01:18:40,702 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 7 states. [2018-06-25 01:18:40,933 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:18:40,933 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 01:18:40,933 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 01:18:40,933 INFO ]: Start accepts. Automaton has 7 states. Word has length 8 [2018-06-25 01:18:40,933 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:18:40,934 INFO ]: With dead ends: 10 [2018-06-25 01:18:40,934 INFO ]: Without dead ends: 10 [2018-06-25 01:18:40,934 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 5 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=43, Invalid=67, Unknown=0, NotChecked=0, Total=110 [2018-06-25 01:18:40,934 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 01:18:40,937 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 01:18:40,937 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 01:18:40,938 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 01:18:40,938 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 01:18:40,938 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:18:40,938 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 01:18:40,938 INFO ]: Interpolant automaton has 7 states. [2018-06-25 01:18:40,938 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 01:18:40,938 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 01:18:40,938 INFO ]: Found error trace [2018-06-25 01:18:40,938 INFO ]: trace histogram [4, 1, 1, 1, 1, 1] [2018-06-25 01:18:40,938 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:40,938 INFO ]: Analyzing trace with hash 1201538306, now seen corresponding path program 4 times [2018-06-25 01:18:40,938 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:40,938 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:40,939 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:40,939 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:18:40,939 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:41,000 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:41,690 WARN ]: Spent 486.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-25 01:18:42,349 WARN ]: Spent 597.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 16 [2018-06-25 01:18:42,373 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:42,374 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:18:42,374 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 01:18:42,381 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 01:18:42,449 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 01:18:42,449 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:42,453 INFO ]: Computing forward predicates... [2018-06-25 01:18:43,382 WARN ]: Spent 226.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 8 [2018-06-25 01:18:53,377 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:53,398 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:18:53,398 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-25 01:18:53,398 INFO ]: Interpolant automaton has 9 states [2018-06-25 01:18:53,398 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 01:18:53,398 INFO ]: CoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-25 01:18:53,398 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 9 states. [2018-06-25 01:18:53,642 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:18:53,643 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 01:18:53,643 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 01:18:53,643 INFO ]: Start accepts. Automaton has 9 states. Word has length 9 [2018-06-25 01:18:53,643 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:18:53,643 INFO ]: With dead ends: 11 [2018-06-25 01:18:53,643 INFO ]: Without dead ends: 11 [2018-06-25 01:18:53,643 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 5 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=66, Invalid=116, Unknown=0, NotChecked=0, Total=182 [2018-06-25 01:18:53,643 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 01:18:53,645 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 01:18:53,645 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 01:18:53,645 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 01:18:53,646 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 01:18:53,646 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:18:53,646 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 01:18:53,646 INFO ]: Interpolant automaton has 9 states. [2018-06-25 01:18:53,646 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 01:18:53,646 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 01:18:53,646 INFO ]: Found error trace [2018-06-25 01:18:53,646 INFO ]: trace histogram [5, 1, 1, 1, 1, 1] [2018-06-25 01:18:53,646 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:53,646 INFO ]: Analyzing trace with hash -1407314007, now seen corresponding path program 5 times [2018-06-25 01:18:53,646 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:53,646 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:53,647 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:53,647 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:18:53,647 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:53,699 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:54,069 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:54,069 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:18:54,069 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 01:18:54,075 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 01:18:54,149 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 01:18:54,149 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:54,154 INFO ]: Computing forward predicates... [2018-06-25 01:18:56,034 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:18:57,588 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:18:58,198 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:58,219 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 01:18:58,219 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-25 01:18:58,219 INFO ]: Interpolant automaton has 9 states [2018-06-25 01:18:58,220 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 01:18:58,220 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-25 01:18:58,220 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 9 states. [2018-06-25 01:18:58,541 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 01:18:58,541 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 01:18:58,599 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 01:18:58,599 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-25 01:18:58,599 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 01:18:58,599 INFO ]: With dead ends: 12 [2018-06-25 01:18:58,599 INFO ]: Without dead ends: 12 [2018-06-25 01:18:58,600 INFO ]: 0 DeclaredPredicates, 23 GetRequests, 5 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=75, Invalid=135, Unknown=0, NotChecked=0, Total=210 [2018-06-25 01:18:58,600 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 01:18:58,601 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 01:18:58,601 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 01:18:58,601 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 01:18:58,601 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 01:18:58,601 INFO ]: Finished accepts. word is rejected. [2018-06-25 01:18:58,601 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 01:18:58,601 INFO ]: Interpolant automaton has 9 states. [2018-06-25 01:18:58,601 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 01:18:58,602 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 01:18:58,602 INFO ]: Found error trace [2018-06-25 01:18:58,602 INFO ]: trace histogram [6, 1, 1, 1, 1, 1] [2018-06-25 01:18:58,602 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 01:18:58,602 INFO ]: Analyzing trace with hash -677357086, now seen corresponding path program 6 times [2018-06-25 01:18:58,602 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 01:18:58,602 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 01:18:58,602 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:58,602 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 01:18:58,603 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 01:18:58,685 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:59,005 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 01:18:59,006 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 01:18:59,006 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 01:18:59,026 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 01:18:59,091 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-25 01:18:59,091 INFO ]: Conjunction of SSA is unsat [2018-06-25 01:18:59,095 INFO ]: Computing forward predicates... [2018-06-25 01:19:03,492 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:19:03,495 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:19:03,498 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 01:19:03,513 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 01:19:03,883 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:19:03,884 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 01:19:03,999 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:19:04,023 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 01:19:04,025 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 01:19:04,034 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 01:19:34,489 INFO ]: Timeout while computing interpolants [2018-06-25 01:19:34,690 WARN ]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 01:19:34,690 WARN ]: Verification canceled [2018-06-25 01:19:34,692 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-25 01:19:34,693 WARN ]: Timeout [2018-06-25 01:19:34,694 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:19:34 BasicIcfg [2018-06-25 01:19:34,694 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 01:19:34,694 INFO ]: Toolchain (without parser) took 64882.66 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 257.9 MB in the beginning and 929.6 MB in the end (delta: -671.7 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-25 01:19:34,695 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 274.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 01:19:34,696 INFO ]: ChcToBoogie took 52.46 ms. Allocated memory is still 308.8 MB. Free memory was 257.9 MB in the beginning and 255.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:19:34,696 INFO ]: Boogie Preprocessor took 57.57 ms. Allocated memory is still 308.8 MB. Free memory was 255.9 MB in the beginning and 253.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:19:34,697 INFO ]: RCFGBuilder took 307.79 ms. Allocated memory is still 308.8 MB. Free memory was 253.9 MB in the beginning and 242.0 MB in the end (delta: 11.9 MB). Peak memory consumption was 11.9 MB. Max. memory is 3.6 GB. [2018-06-25 01:19:34,697 INFO ]: BlockEncodingV2 took 128.51 ms. Allocated memory is still 308.8 MB. Free memory was 242.0 MB in the beginning and 237.1 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. [2018-06-25 01:19:34,698 INFO ]: TraceAbstraction took 64328.03 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.1 MB in the beginning and 929.6 MB in the end (delta: -692.5 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 01:19:34,703 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 10 locations, 10 edges - StatisticsResult: Encoded RCFG 6 locations, 6 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 274.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 52.46 ms. Allocated memory is still 308.8 MB. Free memory was 257.9 MB in the beginning and 255.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 57.57 ms. Allocated memory is still 308.8 MB. Free memory was 255.9 MB in the beginning and 253.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 307.79 ms. Allocated memory is still 308.8 MB. Free memory was 253.9 MB in the beginning and 242.0 MB in the end (delta: 11.9 MB). Peak memory consumption was 11.9 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 128.51 ms. Allocated memory is still 308.8 MB. Free memory was 242.0 MB in the beginning and 237.1 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64328.03 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.1 MB in the beginning and 929.6 MB in the end (delta: -692.5 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 Cancelled while BasicCegarLoop was analyzing trace of length 12 with TraceHistMax 6, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 28023 quantified variables from 17 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 64.2s OverallTime, 7 OverallIterations, 6 TraceHistogramMax, 1.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 30 SDtfs, 0 SDslu, 72 SDs, 0 SdLazy, 46 SolverSat, 25 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 86 GetRequests, 28 SyntacticMatches, 13 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 3.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=12occurred in iteration=6, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 25.8s InterpolantComputationTime, 85 NumberOfCodeBlocks, 85 NumberOfCodeBlocksAsserted, 17 NumberOfCheckSat, 74 ConstructedInterpolants, 0 QuantifiedInterpolants, 3194 SizeOfPredicates, 30 NumberOfNonLiveVariables, 1165 ConjunctsInSsa, 173 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 0/70 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/nest-len.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-25_01-19-34-731.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nest-len.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-25_01-19-34-731.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nest-len.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-25_01-19-34-731.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nest-len.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_01-19-34-731.csv Completed graceful shutdown