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-62c3406-m [2018-06-26 21:45:21,428 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 21:45:21,430 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 21:45:21,441 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 21:45:21,441 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 21:45:21,442 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 21:45:21,445 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 21:45:21,449 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 21:45:21,452 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 21:45:21,453 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 21:45:21,454 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 21:45:21,454 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 21:45:21,455 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 21:45:21,458 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 21:45:21,459 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 21:45:21,459 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 21:45:21,460 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 21:45:21,473 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 21:45:21,475 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 21:45:21,476 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 21:45:21,477 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 21:45:21,478 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 21:45:21,480 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 21:45:21,480 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 21:45:21,480 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 21:45:21,484 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 21:45:21,485 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 21:45:21,485 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 21:45:21,486 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 21:45:21,490 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 21:45:21,490 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 21:45:21,490 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 21:45:21,491 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 21:45:21,491 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 21:45:21,491 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 21:45:21,492 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 21:45:21,492 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-26 21:45:21,518 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 21:45:21,518 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 21:45:21,519 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 21:45:21,519 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 21:45:21,521 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 21:45:21,521 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 21:45:21,521 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 21:45:21,521 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 21:45:21,521 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 21:45:21,522 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 21:45:21,522 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 21:45:21,522 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 21:45:21,522 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 21:45:21,522 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 21:45:21,522 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 21:45:21,523 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 21:45:21,523 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 21:45:21,523 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 21:45:21,523 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 21:45:21,523 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 21:45:21,523 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 21:45:21,526 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 21:45:21,526 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 21:45:21,574 INFO ]: Repository-Root is: /tmp [2018-06-26 21:45:21,590 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 21:45:21,594 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 21:45:21,595 INFO ]: Initializing SmtParser... [2018-06-26 21:45:21,595 INFO ]: SmtParser initialized [2018-06-26 21:45:21,596 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-len.c.smt2 [2018-06-26 21:45:21,597 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-26 21:45:21,683 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-len.c.smt2 unknown [2018-06-26 21:45:22,047 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nest-len.c.smt2 [2018-06-26 21:45:22,051 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 21:45:22,058 INFO ]: Walking toolchain with 5 elements. [2018-06-26 21:45:22,059 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 21:45:22,059 INFO ]: Initializing ChcToBoogie... [2018-06-26 21:45:22,059 INFO ]: ChcToBoogie initialized [2018-06-26 21:45:22,062 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,120 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22 Unit [2018-06-26 21:45:22,120 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 21:45:22,121 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 21:45:22,121 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 21:45:22,121 INFO ]: Boogie Preprocessor initialized [2018-06-26 21:45:22,146 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,146 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,152 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,152 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,158 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,160 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,162 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,164 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 21:45:22,165 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 21:45:22,165 INFO ]: Initializing RCFGBuilder... [2018-06-26 21:45:22,165 INFO ]: RCFGBuilder initialized [2018-06-26 21:45:22,166 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (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-26 21:45:22,178 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 21:45:22,178 INFO ]: Found specification of procedure gotoProc [2018-06-26 21:45:22,178 INFO ]: Found implementation of procedure gotoProc [2018-06-26 21:45:22,178 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 21:45:22,178 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 21:45:22,178 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-26 21:45:22,451 INFO ]: Using library mode [2018-06-26 21:45:22,452 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:45:22 BoogieIcfgContainer [2018-06-26 21:45:22,452 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 21:45:22,452 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 21:45:22,452 INFO ]: Initializing BlockEncodingV2... [2018-06-26 21:45:22,453 INFO ]: BlockEncodingV2 initialized [2018-06-26 21:45:22,454 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:45:22" (1/1) ... [2018-06-26 21:45:22,467 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-26 21:45:22,469 INFO ]: Using Remove infeasible edges [2018-06-26 21:45:22,469 INFO ]: Using Maximize final states [2018-06-26 21:45:22,469 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 21:45:22,470 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 21:45:22,471 INFO ]: Using Remove sink states [2018-06-26 21:45:22,472 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 21:45:22,472 INFO ]: Using Use SBE [2018-06-26 21:45:22,477 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:22,490 WARN ]: aborting because of expected exponential blowup for input size 53 [2018-06-26 21:45:22,497 INFO ]: SBE split 0 edges [2018-06-26 21:45:22,502 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-26 21:45:22,504 INFO ]: 0 new accepting states [2018-06-26 21:45:22,553 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-26 21:45:22,555 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:45:22,560 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 21:45:22,560 INFO ]: 0 new accepting states [2018-06-26 21:45:22,560 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 21:45:22,560 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:45:22,560 INFO ]: Encoded RCFG 6 locations, 6 edges [2018-06-26 21:45:22,561 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:45:22 BasicIcfg [2018-06-26 21:45:22,561 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 21:45:22,562 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 21:45:22,562 INFO ]: Initializing TraceAbstraction... [2018-06-26 21:45:22,568 INFO ]: TraceAbstraction initialized [2018-06-26 21:45:22,568 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:45:22" (1/4) ... [2018-06-26 21:45:22,569 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4eb2197e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 09:45:22, skipping insertion in model container [2018-06-26 21:45:22,569 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:45:22" (2/4) ... [2018-06-26 21:45:22,569 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4eb2197e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 09:45:22, skipping insertion in model container [2018-06-26 21:45:22,570 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:45:22" (3/4) ... [2018-06-26 21:45:22,570 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4eb2197e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:45:22, skipping insertion in model container [2018-06-26 21:45:22,570 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:45:22" (4/4) ... [2018-06-26 21:45:22,571 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 21:45:22,579 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 21:45:22,586 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 21:45:22,627 INFO ]: Using default assertion order modulation [2018-06-26 21:45:22,627 INFO ]: Interprodecural is true [2018-06-26 21:45:22,627 INFO ]: Hoare is false [2018-06-26 21:45:22,627 INFO ]: Compute interpolants for FPandBP [2018-06-26 21:45:22,627 INFO ]: Backedges is TWOTRACK [2018-06-26 21:45:22,627 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 21:45:22,627 INFO ]: Difference is false [2018-06-26 21:45:22,627 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 21:45:22,628 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 21:45:22,639 INFO ]: Start isEmpty. Operand 6 states. [2018-06-26 21:45:22,649 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 21:45:22,649 INFO ]: Found error trace [2018-06-26 21:45:22,650 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 21:45:22,650 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:22,655 INFO ]: Analyzing trace with hash 35402562, now seen corresponding path program 1 times [2018-06-26 21:45:22,657 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:22,658 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:22,696 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:22,696 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:45:22,696 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:22,748 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:22,839 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:22,841 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:45:22,841 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:45:22,842 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:45:22,853 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:45:22,853 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:45:22,856 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-26 21:45:22,941 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:45:22,941 INFO ]: Finished difference Result 7 states and 7 transitions. [2018-06-26 21:45:22,944 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:45:22,945 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 21:45:22,945 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:45:22,954 INFO ]: With dead ends: 7 [2018-06-26 21:45:22,954 INFO ]: Without dead ends: 7 [2018-06-26 21:45:22,956 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-26 21:45:22,969 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-26 21:45:22,988 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-26 21:45:22,989 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-26 21:45:22,990 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-06-26 21:45:22,991 INFO ]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-06-26 21:45:22,991 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:45:22,991 INFO ]: Abstraction has 7 states and 7 transitions. [2018-06-26 21:45:22,991 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:45:22,991 INFO ]: Start isEmpty. Operand 7 states and 7 transitions. [2018-06-26 21:45:22,991 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:45:22,991 INFO ]: Found error trace [2018-06-26 21:45:22,992 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:45:22,992 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:22,992 INFO ]: Analyzing trace with hash 1097183593, now seen corresponding path program 1 times [2018-06-26 21:45:22,992 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:22,992 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:22,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:22,993 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:45:22,993 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:23,081 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:23,439 WARN ]: Spent 165.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-26 21:45:23,440 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:23,440 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:45:23,440 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-26 21:45:23,456 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:45:23,521 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:23,531 INFO ]: Computing forward predicates... [2018-06-26 21:45:24,013 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:24,044 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:45:24,044 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-26 21:45:24,044 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:45:24,045 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:45:24,045 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:45:24,045 INFO ]: Start difference. First operand 7 states and 7 transitions. Second operand 5 states. [2018-06-26 21:45:24,243 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:45:24,243 INFO ]: Finished difference Result 8 states and 8 transitions. [2018-06-26 21:45:24,244 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 21:45:24,244 INFO ]: Start accepts. Automaton has 5 states. Word has length 6 [2018-06-26 21:45:24,244 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:45:24,244 INFO ]: With dead ends: 8 [2018-06-26 21:45:24,244 INFO ]: Without dead ends: 8 [2018-06-26 21:45:24,245 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-26 21:45:24,245 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-26 21:45:24,246 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-26 21:45:24,246 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-26 21:45:24,246 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-06-26 21:45:24,246 INFO ]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-06-26 21:45:24,246 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:45:24,246 INFO ]: Abstraction has 8 states and 8 transitions. [2018-06-26 21:45:24,246 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:45:24,246 INFO ]: Start isEmpty. Operand 8 states and 8 transitions. [2018-06-26 21:45:24,247 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 21:45:24,247 INFO ]: Found error trace [2018-06-26 21:45:24,247 INFO ]: trace histogram [2, 1, 1, 1, 1, 1] [2018-06-26 21:45:24,247 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:24,247 INFO ]: Analyzing trace with hash -347342814, now seen corresponding path program 2 times [2018-06-26 21:45:24,247 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:24,247 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:24,248 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:24,248 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:45:24,248 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:24,342 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:24,683 WARN ]: Spent 144.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-26 21:45:24,725 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:24,725 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:45:24,725 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-26 21:45:24,732 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 21:45:24,809 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:45:24,809 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:24,812 INFO ]: Computing forward predicates... [2018-06-26 21:45:26,736 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:26,756 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:45:26,756 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-26 21:45:26,756 INFO ]: Interpolant automaton has 6 states [2018-06-26 21:45:26,756 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 21:45:26,756 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:45:26,757 INFO ]: Start difference. First operand 8 states and 8 transitions. Second operand 6 states. [2018-06-26 21:45:27,078 WARN ]: Spent 203.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-26 21:45:27,087 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:45:27,087 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-26 21:45:27,087 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 21:45:27,087 INFO ]: Start accepts. Automaton has 6 states. Word has length 7 [2018-06-26 21:45:27,087 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:45:27,087 INFO ]: With dead ends: 9 [2018-06-26 21:45:27,087 INFO ]: Without dead ends: 9 [2018-06-26 21:45:27,088 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 6 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=26, Invalid=30, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:45:27,088 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 21:45:27,089 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-26 21:45:27,089 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 21:45:27,089 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-26 21:45:27,089 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-26 21:45:27,089 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:45:27,090 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-26 21:45:27,090 INFO ]: Interpolant automaton has 6 states. [2018-06-26 21:45:27,090 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-26 21:45:27,090 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 21:45:27,090 INFO ]: Found error trace [2018-06-26 21:45:27,090 INFO ]: trace histogram [3, 1, 1, 1, 1, 1] [2018-06-26 21:45:27,090 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:27,090 INFO ]: Analyzing trace with hash 2116978825, now seen corresponding path program 3 times [2018-06-26 21:45:27,090 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:27,090 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:27,091 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:27,091 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:45:27,091 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:27,135 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:27,320 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:27,320 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:45:27,320 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-26 21:45:27,333 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 21:45:27,401 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-26 21:45:27,401 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:27,404 INFO ]: Computing forward predicates... [2018-06-26 21:45:32,883 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:32,903 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:45:32,903 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-26 21:45:32,903 INFO ]: Interpolant automaton has 7 states [2018-06-26 21:45:32,903 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 21:45:32,904 INFO ]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:45:32,904 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 7 states. [2018-06-26 21:45:33,119 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:45:33,119 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-26 21:45:33,119 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:45:33,119 INFO ]: Start accepts. Automaton has 7 states. Word has length 8 [2018-06-26 21:45:33,119 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:45:33,119 INFO ]: With dead ends: 10 [2018-06-26 21:45:33,119 INFO ]: Without dead ends: 10 [2018-06-26 21:45:33,120 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-26 21:45:33,120 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-26 21:45:33,121 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-26 21:45:33,121 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-26 21:45:33,121 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-26 21:45:33,121 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-26 21:45:33,121 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:45:33,121 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-26 21:45:33,121 INFO ]: Interpolant automaton has 7 states. [2018-06-26 21:45:33,121 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-26 21:45:33,121 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-26 21:45:33,121 INFO ]: Found error trace [2018-06-26 21:45:33,121 INFO ]: trace histogram [4, 1, 1, 1, 1, 1] [2018-06-26 21:45:33,122 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:33,122 INFO ]: Analyzing trace with hash 1201538306, now seen corresponding path program 4 times [2018-06-26 21:45:33,122 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:33,122 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:33,123 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:33,123 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:45:33,123 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:33,169 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:33,796 WARN ]: Spent 439.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-26 21:45:33,887 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:33,887 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:45:33,887 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-26 21:45:33,895 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 21:45:33,959 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 21:45:33,959 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:33,963 INFO ]: Computing forward predicates... [2018-06-26 21:45:35,822 WARN ]: Spent 204.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 8 [2018-06-26 21:45:46,027 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:46,046 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:45:46,046 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-26 21:45:46,046 INFO ]: Interpolant automaton has 9 states [2018-06-26 21:45:46,047 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 21:45:46,047 INFO ]: CoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:45:46,047 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 9 states. [2018-06-26 21:45:46,366 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 18 [2018-06-26 21:45:46,367 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:45:46,367 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-26 21:45:46,367 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 21:45:46,367 INFO ]: Start accepts. Automaton has 9 states. Word has length 9 [2018-06-26 21:45:46,367 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:45:46,368 INFO ]: With dead ends: 11 [2018-06-26 21:45:46,368 INFO ]: Without dead ends: 11 [2018-06-26 21:45:46,368 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 5 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=66, Invalid=116, Unknown=0, NotChecked=0, Total=182 [2018-06-26 21:45:46,368 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-26 21:45:46,369 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-26 21:45:46,369 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 21:45:46,369 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-26 21:45:46,369 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-26 21:45:46,369 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:45:46,369 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-26 21:45:46,369 INFO ]: Interpolant automaton has 9 states. [2018-06-26 21:45:46,369 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-26 21:45:46,370 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 21:45:46,370 INFO ]: Found error trace [2018-06-26 21:45:46,370 INFO ]: trace histogram [5, 1, 1, 1, 1, 1] [2018-06-26 21:45:46,370 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:46,370 INFO ]: Analyzing trace with hash -1407314007, now seen corresponding path program 5 times [2018-06-26 21:45:46,370 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:46,370 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:46,370 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:46,370 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:45:46,370 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:46,418 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:46,714 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:46,714 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:45:46,714 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-26 21:45:46,720 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 21:45:46,793 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-26 21:45:46,793 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:46,797 INFO ]: Computing forward predicates... [2018-06-26 21:45:47,999 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:49,544 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:50,706 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:50,726 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:45:50,726 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-26 21:45:50,726 INFO ]: Interpolant automaton has 9 states [2018-06-26 21:45:50,726 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 21:45:50,726 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:45:50,726 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 9 states. [2018-06-26 21:45:51,041 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:45:51,041 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-26 21:45:51,097 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-26 21:45:51,097 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-26 21:45:51,097 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:45:51,097 INFO ]: With dead ends: 12 [2018-06-26 21:45:51,097 INFO ]: Without dead ends: 12 [2018-06-26 21:45:51,098 INFO ]: 0 DeclaredPredicates, 23 GetRequests, 5 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=75, Invalid=135, Unknown=0, NotChecked=0, Total=210 [2018-06-26 21:45:51,098 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-26 21:45:51,099 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-26 21:45:51,099 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-26 21:45:51,099 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-26 21:45:51,099 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-26 21:45:51,099 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:45:51,099 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-26 21:45:51,099 INFO ]: Interpolant automaton has 9 states. [2018-06-26 21:45:51,099 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-26 21:45:51,100 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 21:45:51,100 INFO ]: Found error trace [2018-06-26 21:45:51,100 INFO ]: trace histogram [6, 1, 1, 1, 1, 1] [2018-06-26 21:45:51,100 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:45:51,100 INFO ]: Analyzing trace with hash -677357086, now seen corresponding path program 6 times [2018-06-26 21:45:51,100 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:45:51,100 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:45:51,101 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:51,101 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:45:51,101 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:45:51,172 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:51,487 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:45:51,487 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:45:51,487 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-26 21:45:51,493 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 21:45:51,559 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-26 21:45:51,559 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:45:51,563 INFO ]: Computing forward predicates... [2018-06-26 21:45:55,904 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:55,905 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:55,906 WARN ]: expecting exponential blowup for input size 8 [2018-06-26 21:45:55,911 WARN ]: expecting exponential blowup for input size 8 [2018-06-26 21:45:56,099 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:56,100 WARN ]: expecting exponential blowup for input size 8 [2018-06-26 21:45:56,131 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:56,152 WARN ]: expecting exponential blowup for input size 6 [2018-06-26 21:45:56,153 WARN ]: expecting exponential blowup for input size 8 [2018-06-26 21:45:56,157 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-26 21:46:29,380 INFO ]: Timeout while computing interpolants [2018-06-26 21:46:29,581 WARN ]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:46:29,581 WARN ]: Verification canceled [2018-06-26 21:46:29,583 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 21:46:29,584 WARN ]: Timeout [2018-06-26 21:46:29,584 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:46:29 BasicIcfg [2018-06-26 21:46:29,584 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 21:46:29,584 INFO ]: Toolchain (without parser) took 67532.49 ms. Allocated memory was 309.9 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 258.2 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-26 21:46:29,585 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 21:46:29,585 INFO ]: ChcToBoogie took 62.18 ms. Allocated memory is still 309.9 MB. Free memory was 258.2 MB in the beginning and 256.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:46:29,586 INFO ]: Boogie Preprocessor took 43.10 ms. Allocated memory is still 309.9 MB. Free memory was 256.2 MB in the beginning and 254.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:46:29,586 INFO ]: RCFGBuilder took 286.87 ms. Allocated memory is still 309.9 MB. Free memory was 254.2 MB in the beginning and 241.2 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:46:29,587 INFO ]: BlockEncodingV2 took 108.82 ms. Allocated memory is still 309.9 MB. Free memory was 241.2 MB in the beginning and 237.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:46:29,587 INFO ]: TraceAbstraction took 67021.61 ms. Allocated memory was 309.9 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.2 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-26 21:46:29,591 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.06 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 62.18 ms. Allocated memory is still 309.9 MB. Free memory was 258.2 MB in the beginning and 256.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 43.10 ms. Allocated memory is still 309.9 MB. Free memory was 256.2 MB in the beginning and 254.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 286.87 ms. Allocated memory is still 309.9 MB. Free memory was 254.2 MB in the beginning and 241.2 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 108.82 ms. Allocated memory is still 309.9 MB. Free memory was 241.2 MB in the beginning and 237.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 67021.61 ms. Allocated memory was 309.9 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.2 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). 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 20375 quantified variables from 17 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 66.9s OverallTime, 7 OverallIterations, 6 TraceHistogramMax, 1.5s 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.5s 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.9s 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-26_21-46-29-605.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-26_21-46-29-605.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-26_21-46-29-605.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-26_21-46-29-605.csv Completed graceful shutdown