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/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 19:20:41,842 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 19:20:41,844 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 19:20:41,858 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 19:20:41,858 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 19:20:41,859 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 19:20:41,860 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 19:20:41,867 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 19:20:41,869 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 19:20:41,870 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 19:20:41,870 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 19:20:41,871 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 19:20:41,872 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 19:20:41,874 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 19:20:41,875 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 19:20:41,875 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 19:20:41,876 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 19:20:41,880 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 19:20:41,881 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 19:20:41,891 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 19:20:41,892 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 19:20:41,893 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 19:20:41,895 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 19:20:41,895 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 19:20:41,895 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 19:20:41,898 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 19:20:41,898 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 19:20:41,899 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 19:20:41,900 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 19:20:41,900 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 19:20:41,902 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 19:20:41,903 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 19:20:41,903 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 19:20:41,903 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 19:20:41,904 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 19:20:41,905 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 19:20:41,905 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-26 19:20:41,926 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 19:20:41,927 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 19:20:41,927 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 19:20:41,928 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 19:20:41,929 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 19:20:41,929 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 19:20:41,929 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 19:20:41,929 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 19:20:41,929 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 19:20:41,930 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 19:20:41,930 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 19:20:41,930 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 19:20:41,930 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 19:20:41,930 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 19:20:41,931 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 19:20:41,931 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 19:20:41,931 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 19:20:41,931 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 19:20:41,931 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 19:20:41,931 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 19:20:41,932 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 19:20:41,933 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 19:20:41,933 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 19:20:41,981 INFO ]: Repository-Root is: /tmp [2018-06-26 19:20:41,995 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 19:20:41,999 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 19:20:42,000 INFO ]: Initializing SmtParser... [2018-06-26 19:20:42,000 INFO ]: SmtParser initialized [2018-06-26 19:20:42,001 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 [2018-06-26 19:20:42,002 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 19:20:42,089 INFO ]: Executing SMT file /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 unknown [2018-06-26 19:20:42,456 INFO ]: Succesfully executed SMT file /storage/chc-comp/sally-chc-benchmarks/misc/frolloc_lifo_prop2.smt2 [2018-06-26 19:20:42,460 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 19:20:42,476 INFO ]: Walking toolchain with 5 elements. [2018-06-26 19:20:42,476 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 19:20:42,476 INFO ]: Initializing ChcToBoogie... [2018-06-26 19:20:42,476 INFO ]: ChcToBoogie initialized [2018-06-26 19:20:42,485 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,583 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42 Unit [2018-06-26 19:20:42,583 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 19:20:42,583 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 19:20:42,583 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 19:20:42,583 INFO ]: Boogie Preprocessor initialized [2018-06-26 19:20:42,606 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,606 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,628 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,629 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,645 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,646 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,648 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (1/1) ... [2018-06-26 19:20:42,652 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 19:20:42,653 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 19:20:42,653 INFO ]: Initializing RCFGBuilder... [2018-06-26 19:20:42,653 INFO ]: RCFGBuilder initialized [2018-06-26 19:20:42,653 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (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 19:20:42,678 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 19:20:42,678 INFO ]: Found specification of procedure gotoProc [2018-06-26 19:20:42,678 INFO ]: Found implementation of procedure gotoProc [2018-06-26 19:20:42,678 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 19:20:42,678 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 19:20:42,678 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 19:20:43,079 INFO ]: Using library mode [2018-06-26 19:20:43,079 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 07:20:43 BoogieIcfgContainer [2018-06-26 19:20:43,079 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 19:20:43,080 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 19:20:43,080 INFO ]: Initializing BlockEncodingV2... [2018-06-26 19:20:43,081 INFO ]: BlockEncodingV2 initialized [2018-06-26 19:20:43,081 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 07:20:43" (1/1) ... [2018-06-26 19:20:43,097 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-26 19:20:43,100 INFO ]: Using Remove infeasible edges [2018-06-26 19:20:43,100 INFO ]: Using Maximize final states [2018-06-26 19:20:43,101 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 19:20:43,101 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 19:20:43,103 INFO ]: Using Remove sink states [2018-06-26 19:20:43,107 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 19:20:43,107 INFO ]: Using Use SBE [2018-06-26 19:20:43,629 INFO ]: SBE split 1 edges [2018-06-26 19:20:43,663 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-26 19:20:43,664 INFO ]: 0 new accepting states [2018-06-26 19:20:43,731 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-26 19:20:43,733 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 19:20:43,770 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 19:20:43,771 INFO ]: 0 new accepting states [2018-06-26 19:20:43,772 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 19:20:43,772 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 19:20:43,810 INFO ]: Encoded RCFG 6 locations, 321 edges [2018-06-26 19:20:43,811 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 07:20:43 BasicIcfg [2018-06-26 19:20:43,811 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 19:20:43,813 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 19:20:43,813 INFO ]: Initializing TraceAbstraction... [2018-06-26 19:20:43,816 INFO ]: TraceAbstraction initialized [2018-06-26 19:20:43,816 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 07:20:42" (1/4) ... [2018-06-26 19:20:43,817 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2dcdccf5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 07:20:43, skipping insertion in model container [2018-06-26 19:20:43,817 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 07:20:42" (2/4) ... [2018-06-26 19:20:43,817 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2dcdccf5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 07:20:43, skipping insertion in model container [2018-06-26 19:20:43,818 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 07:20:43" (3/4) ... [2018-06-26 19:20:43,818 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2dcdccf5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 07:20:43, skipping insertion in model container [2018-06-26 19:20:43,818 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 07:20:43" (4/4) ... [2018-06-26 19:20:43,819 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 19:20:43,830 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 19:20:43,837 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 19:20:43,887 INFO ]: Using default assertion order modulation [2018-06-26 19:20:43,887 INFO ]: Interprodecural is true [2018-06-26 19:20:43,887 INFO ]: Hoare is false [2018-06-26 19:20:43,887 INFO ]: Compute interpolants for FPandBP [2018-06-26 19:20:43,887 INFO ]: Backedges is TWOTRACK [2018-06-26 19:20:43,887 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 19:20:43,887 INFO ]: Difference is false [2018-06-26 19:20:43,887 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 19:20:43,887 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 19:20:43,901 INFO ]: Start isEmpty. Operand 6 states. [2018-06-26 19:20:43,917 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 19:20:43,918 INFO ]: Found error trace [2018-06-26 19:20:43,918 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 19:20:43,918 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 19:20:43,923 INFO ]: Analyzing trace with hash 45120194, now seen corresponding path program 1 times [2018-06-26 19:20:43,925 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 19:20:43,925 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 19:20:43,971 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:43,971 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 19:20:43,971 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:44,060 INFO ]: Conjunction of SSA is unsat [2018-06-26 19:20:44,219 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 19:20:44,222 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 19:20:44,222 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 19:20:44,224 INFO ]: Interpolant automaton has 3 states [2018-06-26 19:20:44,240 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 19:20:44,240 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 19:20:44,243 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-26 19:20:47,936 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 19:20:47,936 INFO ]: Finished difference Result 7 states and 314 transitions. [2018-06-26 19:20:47,939 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 19:20:47,940 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 19:20:47,940 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 19:20:47,955 INFO ]: With dead ends: 7 [2018-06-26 19:20:47,955 INFO ]: Without dead ends: 7 [2018-06-26 19:20:47,957 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 19:20:47,976 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-26 19:20:47,997 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-26 19:20:47,998 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-26 19:20:48,000 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 314 transitions. [2018-06-26 19:20:48,001 INFO ]: Start accepts. Automaton has 7 states and 314 transitions. Word has length 5 [2018-06-26 19:20:48,002 INFO ]: Finished accepts. word is rejected. [2018-06-26 19:20:48,002 INFO ]: Abstraction has 7 states and 314 transitions. [2018-06-26 19:20:48,002 INFO ]: Interpolant automaton has 3 states. [2018-06-26 19:20:48,002 INFO ]: Start isEmpty. Operand 7 states and 314 transitions. [2018-06-26 19:20:48,002 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 19:20:48,002 INFO ]: Found error trace [2018-06-26 19:20:48,002 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 19:20:48,002 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 19:20:48,003 INFO ]: Analyzing trace with hash 1391613812, now seen corresponding path program 1 times [2018-06-26 19:20:48,003 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 19:20:48,003 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 19:20:48,003 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:48,004 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 19:20:48,004 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:48,058 INFO ]: Conjunction of SSA is unsat [2018-06-26 19:20:48,153 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 19:20:48,153 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 19:20:48,153 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 19:20:48,155 INFO ]: Interpolant automaton has 3 states [2018-06-26 19:20:48,155 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 19:20:48,155 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 19:20:48,155 INFO ]: Start difference. First operand 7 states and 314 transitions. Second operand 3 states. [2018-06-26 19:20:49,367 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 19:20:49,367 INFO ]: Finished difference Result 9 states and 515 transitions. [2018-06-26 19:20:49,367 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 19:20:49,367 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-26 19:20:49,368 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 19:20:49,369 INFO ]: With dead ends: 9 [2018-06-26 19:20:49,369 INFO ]: Without dead ends: 9 [2018-06-26 19:20:49,370 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 19:20:49,370 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 19:20:49,379 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-26 19:20:49,379 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 19:20:49,381 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 515 transitions. [2018-06-26 19:20:49,381 INFO ]: Start accepts. Automaton has 9 states and 515 transitions. Word has length 6 [2018-06-26 19:20:49,381 INFO ]: Finished accepts. word is rejected. [2018-06-26 19:20:49,381 INFO ]: Abstraction has 9 states and 515 transitions. [2018-06-26 19:20:49,381 INFO ]: Interpolant automaton has 3 states. [2018-06-26 19:20:49,381 INFO ]: Start isEmpty. Operand 9 states and 515 transitions. [2018-06-26 19:20:49,382 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 19:20:49,382 INFO ]: Found error trace [2018-06-26 19:20:49,382 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-26 19:20:49,382 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 19:20:49,382 INFO ]: Analyzing trace with hash 182051370, now seen corresponding path program 1 times [2018-06-26 19:20:49,382 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 19:20:49,382 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 19:20:49,383 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:49,383 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 19:20:49,383 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:49,429 INFO ]: Conjunction of SSA is unsat [2018-06-26 19:20:49,498 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 19:20:49,498 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 19:20:49,498 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 19:20:49,498 INFO ]: Interpolant automaton has 3 states [2018-06-26 19:20:49,498 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 19:20:49,498 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 19:20:49,498 INFO ]: Start difference. First operand 9 states and 515 transitions. Second operand 3 states. [2018-06-26 19:20:50,790 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 19:20:50,790 INFO ]: Finished difference Result 11 states and 740 transitions. [2018-06-26 19:20:50,790 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 19:20:50,791 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-26 19:20:50,791 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 19:20:50,792 INFO ]: With dead ends: 11 [2018-06-26 19:20:50,792 INFO ]: Without dead ends: 11 [2018-06-26 19:20:50,792 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 19:20:50,792 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-26 19:20:50,803 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-26 19:20:50,803 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 19:20:50,805 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 740 transitions. [2018-06-26 19:20:50,805 INFO ]: Start accepts. Automaton has 11 states and 740 transitions. Word has length 7 [2018-06-26 19:20:50,805 INFO ]: Finished accepts. word is rejected. [2018-06-26 19:20:50,805 INFO ]: Abstraction has 11 states and 740 transitions. [2018-06-26 19:20:50,805 INFO ]: Interpolant automaton has 3 states. [2018-06-26 19:20:50,805 INFO ]: Start isEmpty. Operand 11 states and 740 transitions. [2018-06-26 19:20:50,806 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 19:20:50,806 INFO ]: Found error trace [2018-06-26 19:20:50,806 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 19:20:50,806 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 19:20:50,806 INFO ]: Analyzing trace with hash 1339665930, now seen corresponding path program 1 times [2018-06-26 19:20:50,806 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 19:20:50,806 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 19:20:50,807 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:50,807 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 19:20:50,807 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:50,849 INFO ]: Conjunction of SSA is unsat [2018-06-26 19:20:50,934 INFO ]: Checked inductivity of 6 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-26 19:20:50,934 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 19:20:50,934 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 19:20:50,934 INFO ]: Interpolant automaton has 3 states [2018-06-26 19:20:50,935 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 19:20:50,935 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 19:20:50,935 INFO ]: Start difference. First operand 11 states and 740 transitions. Second operand 3 states. [2018-06-26 19:20:52,604 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 19:20:52,604 INFO ]: Finished difference Result 13 states and 989 transitions. [2018-06-26 19:20:52,605 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 19:20:52,605 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-26 19:20:52,605 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 19:20:52,606 INFO ]: With dead ends: 13 [2018-06-26 19:20:52,606 INFO ]: Without dead ends: 13 [2018-06-26 19:20:52,606 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 19:20:52,606 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-26 19:20:52,612 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-26 19:20:52,613 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 19:20:52,615 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 989 transitions. [2018-06-26 19:20:52,615 INFO ]: Start accepts. Automaton has 13 states and 989 transitions. Word has length 8 [2018-06-26 19:20:52,615 INFO ]: Finished accepts. word is rejected. [2018-06-26 19:20:52,615 INFO ]: Abstraction has 13 states and 989 transitions. [2018-06-26 19:20:52,615 INFO ]: Interpolant automaton has 3 states. [2018-06-26 19:20:52,615 INFO ]: Start isEmpty. Operand 13 states and 989 transitions. [2018-06-26 19:20:52,616 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-26 19:20:52,616 INFO ]: Found error trace [2018-06-26 19:20:52,616 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 19:20:52,616 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 19:20:52,616 INFO ]: Analyzing trace with hash -1421421460, now seen corresponding path program 1 times [2018-06-26 19:20:52,616 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 19:20:52,616 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 19:20:52,617 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:52,617 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 19:20:52,617 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 19:20:52,688 INFO ]: Conjunction of SSA is unsat [2018-06-26 19:20:52,823 INFO ]: Checked inductivity of 10 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 19:20:52,823 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 19:20:52,823 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 19:20:52,836 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 19:20:53,008 INFO ]: Conjunction of SSA is unsat [2018-06-26 19:20:53,020 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-26 19:21:51,556 INFO ]: Timeout while computing interpolants [2018-06-26 19:21:51,781 WARN ]: Destroyed unattended storables created during the last iteration: 3 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 19:21:51,781 WARN ]: Verification canceled [2018-06-26 19:21:51,784 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 19:21:51,785 WARN ]: Timeout [2018-06-26 19:21:51,785 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 07:21:51 BasicIcfg [2018-06-26 19:21:51,785 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 19:21:51,786 INFO ]: Toolchain (without parser) took 69325.48 ms. Allocated memory was 305.1 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 250.4 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.5 GB. Max. memory is 3.6 GB. [2018-06-26 19:21:51,788 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.1 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 19:21:51,788 INFO ]: ChcToBoogie took 107.02 ms. Allocated memory is still 305.1 MB. Free memory was 249.4 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 19:21:51,789 INFO ]: Boogie Preprocessor took 68.59 ms. Allocated memory is still 305.1 MB. Free memory was 247.4 MB in the beginning and 245.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 19:21:51,789 INFO ]: RCFGBuilder took 426.81 ms. Allocated memory is still 305.1 MB. Free memory was 245.4 MB in the beginning and 218.4 MB in the end (delta: 27.0 MB). Peak memory consumption was 27.0 MB. Max. memory is 3.6 GB. [2018-06-26 19:21:51,790 INFO ]: BlockEncodingV2 took 731.17 ms. Allocated memory was 305.1 MB in the beginning and 330.8 MB in the end (delta: 25.7 MB). Free memory was 218.4 MB in the beginning and 230.5 MB in the end (delta: -12.1 MB). Peak memory consumption was 41.3 MB. Max. memory is 3.6 GB. [2018-06-26 19:21:51,790 INFO ]: TraceAbstraction took 67972.60 ms. Allocated memory was 330.8 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 228.9 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.5 GB. Max. memory is 3.6 GB. [2018-06-26 19:21:51,794 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, 321 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 305.1 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 107.02 ms. Allocated memory is still 305.1 MB. Free memory was 249.4 MB in the beginning and 247.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 68.59 ms. Allocated memory is still 305.1 MB. Free memory was 247.4 MB in the beginning and 245.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 426.81 ms. Allocated memory is still 305.1 MB. Free memory was 245.4 MB in the beginning and 218.4 MB in the end (delta: 27.0 MB). Peak memory consumption was 27.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 731.17 ms. Allocated memory was 305.1 MB in the beginning and 330.8 MB in the end (delta: 25.7 MB). Free memory was 218.4 MB in the beginning and 230.5 MB in the end (delta: -12.1 MB). Peak memory consumption was 41.3 MB. Max. memory is 3.6 GB. * TraceAbstraction took 67972.60 ms. Allocated memory was 330.8 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 228.9 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.5 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 10 with TraceHistMax 1, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 3 quantified variables from 16 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 67.9s OverallTime, 5 OverallIterations, 1 TraceHistogramMax, 7.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 20 SDtfs, 0 SDslu, 12 SDs, 0 SdLazy, 1597 SolverSat, 1255 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 7.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred in iteration=4, 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, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 0.4s InterpolantComputationTime, 26 NumberOfCodeBlocks, 26 NumberOfCodeBlocksAsserted, 4 NumberOfCheckSat, 22 ConstructedInterpolants, 0 QuantifiedInterpolants, 166 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 4 InterpolantComputations, 4 PerfectInterpolantSequences, 10/10 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/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_19-21-51-810.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_19-21-51-810.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_19-21-51-810.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/frolloc_lifo_prop2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_19-21-51-810.csv Completed graceful shutdown